프로그래머스_쇠막대기_스택(java)

쇠막대기

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/42585?language=java

여러 개의 쇠막대기를 레이저로 절단하려고 합니다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자릅니다. 쇠막대기와 레이저의 배치를 표현한 문자열 arrangement가 매개변수로 주어질 때, 잘린 쇠막대기 조각의 총 개수를 return 하도록 solution 함수를 작성해주세요.

solution - 1) 어렵게 생각하고 싶은데 방법을 몰라

스트링을 훑어보는 방식으로 시도해봤다.

하지만 이렇게 하니 정확도 테스트 0점... 

    public static void main(String[] args) {
        String arrangement = "()(((()())(())()))(())";
        int count = 0;
        
        int razer = 0;
        int left = 0;
        int right = 0;
        boolean isLeft = false;
        for(int i = 0; i < arrangement.length(); i++) {
            if(arrangement.charAt(i) == '(') {
                left++;
                isLeft = true;
            }else { // equal with ')'
                right++;
                if(isLeft) {razer++; isLeft = false;} // 레이저 수 
                if(right == left) {
                    System.out.print("razer : "+ razer + " / ");
                    System.out.print("left : "+ left + " / ");
                    System.out.println("right : "+ right);
                    if( right != 1) count += razer*(left-razer);
                    System.out.println("count : "+ count);
                    right = 0;
                    left = 0;
                    razer = 0;
                }
            }
        }
        
        System.out.println("count : "+ count);
    }

그래서 다른 방법을 찾아봤더니

스택을 이용하는 쉬운 문제라고 !!

스택 문제는 처음 풀어보는데 

자바에서는 Stack클래스가 있어 이를 이용하면 되었다.

solution - 2) 스택 이용

스택에 '('가 나올때마다 값을 추가하고 

')'가 나오면 레이저인지 확인 후 조각의 갯수를 스택의 크기를 이용해 더해준다.

또한 ')'가 나왔을 시 절단이 중단에 끝난 쇠막대기의 갯수도 세어줘야하기 때문에 레이저인지 확인하고 아니면 +1 을 더해준다. 

import java.util.*;
class Solution {
    public int solution(String arrangement) {
        Stack<Integer> stack = new Stack<Integer>();
        
        int count = 0;
        for(int i = 0; i < arrangement.length(); i++) {
            if(arrangement.charAt(i) == '(') {
                stack.push(1);
            }else {
                stack.pop();
                if(arrangement.charAt(i-1) == '(') count += stack.size();
                else count++;
            } 
            
        }
        return count;
    }
}