백준 2504 괄호의 값 - Stack 구현

문제링크 : 괄호의 값

풀이

문제를 보고 특정한 알고리즘이 아니라 조건문과 반복문을 잘 사용하면 풀 수 있을거같아 구현문제로 판단했다.

실제 테스트케이스를 통해 구현을 어떻게 해야할지 조건을 찾았다.

먼저 실제 저런 기호로 주어진 수식을 풀어보면 한번 확인하면서 문자열을 넘어갈 수 있다. 즉 O(N) 시간에 알고리즘을 해결할 수 있다.

연속된 괄호는 곱셈으로 처리하므로 현재 얼마나 곱셈이 누적되어있는지 변수로 저장할 필요가 있어보였고

괄호가 닫힐때 정답값을 누적시키고 이후 결과로 출력하면 될거같았다.

문제점 1

테스트케이스를 돌려보면 괄호가 닫힐때 무조건 값을 더하면 안된다.

즉, (()) 에서 괄호가 닫힐때 값을 더하면 괄호가 총 2번닫히므로 2+4 = 6이 된다.

이 문제는 )를 만났을때 이전 값이 ( 였는지 확인하면 된다.

public class Main {


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String str = sc.nextLine(); // 길이 1~30

        int n = str.length();

        Stack<Character> stack = new Stack<Character>();

        int mul = 1;
        int ans = 0;
        for (int i = 0; i < n; i++) {

            char ch = str.charAt(i);

            if (ch == '(') {
                mul *= 2;
                stack.push(ch);
            } else if (ch == ')') {
                if (!stack.empty() && stack.peek() == '(') {

                    if (i !=0 && str.charAt(i-1)=='(') {
                        ans += mul;
                    }


                    mul /= 2;
                    stack.pop();
                } else {
                    // 오류발생
                    System.out.println(0);
                    return;
                }
            } else if (ch == '[') {
                mul *= 3;
                stack.push(ch);
            } else {
                // ]일때
                if (!stack.empty() && stack.peek() == '[') {

                    if ( i != 0 && str.charAt(i-1)=='[') {
                        ans += mul;
                    }


                    mul /= 3;
                    stack.pop();
                } else {
                    // 오류발생
                    System.out.println(0);
                    return;
                }
            }
        }

        System.out.println(ans);
    }
}

문제점 2

Stack을 사용했지만 후처리를 해주지 못했다. 즉, 마지막에 stack이 비워졌는지 확인하는 습관을 갖도록 하자.

반례 : ([[[[] 의 정답은 0이여야 함

        if (stack.empty()) {
            System.out.println(ans);
        }
        else{
            System.out.println(0);
        }