[알고리즘] 백준 2504 괄호의 값

백준 2504

시도

Stack의 push와 pop을 이용해 완전/불완전 괄호를 판별해내는 과정에 대한 접근은 맞았다. 그러나 문제는 분배법칙을 구현하는데 어려움이 있어 문제 풀이에 실패하였다.
(가 입력되었을때는 2를 곱하도록 하였고, [가 입력되었을때는 3을 곱하도록 하였다. 이렇게 했을 경우 (()) 또는 [()] 와 같은 모양의 출력에 있어서는 문제가 없었지만, (()[]) 와 같이 분배법칙이 필요한 형태에서 원하는 결과인 10이 아닌 12가 나옴을 확인할 수 있었다.

풀이

코드를 보며 주석을 통해 설명하겠다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        boolean flag = true;

        int result = 0;
        int temp = 1;

        String inputs = br.readLine();

        for (int i = 0; i < inputs.length(); i++) {
            char c = inputs.charAt(i);

            switch (c) {
                case '(':
                    temp *= 2;
                    stack.push(c);
                    break;
                case '[':
                    temp *= 3;
                    stack.push(c);
                    break;
                case ')':
                    // stack이 비어있거나 앞서 (가 스택에 push되어 있지 않을 경우, 불완전한 괄호
                    if (stack.isEmpty() || stack.peek() != '(') {
                        flag = false;
                        break;
                    }
                    // stack이 비어있지 않고, 바로 이전 문자가 (일 경우.
                    // stack.peek()을 쓰지 않는 이유는 (뿐만 아니라 [도 push 되어 있을 수 있기 때문이다.
                    // 이 경우에는 분배법칙을 구현하기 위해 지금까지의 값을 result에 더해 저장한다.
                    if (inputs.charAt(i-1) == '(') {
                        result += temp;
                    }
                    stack.pop(); // )와 짝이 되는 (를 pop 한다.
                    temp /= 2; // (가 push될때 무조건 2를 곱하게 되고, 이미 result에 값이 더해진 이후이므로 다음 계산을 위해 다시 2를 나누어 준다.
                    break;
                case ']':
                    if (stack.isEmpty() || stack.peek() != '[') {
                        flag = false;
                        break;
                    }
                    if (inputs.charAt(i-1) == '[') {
                        result += temp;
                    }
                    stack.pop();
                    temp /= 3;
                    break;
            }
        }

        if (!flag || !stack.isEmpty()) {
            System.out.println(0);
        } else {
            System.out.println(result);
        }
    }
}