[백준]2504번 : 괄호의 값

📌 출처

2504번 : 괄호의 값

📝 문제

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.

⌨ 입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

🖨 출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.

💻 내 코드

1. 리스트를 사용하여 구현

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

public class p2504 {
    private static Stack<String> stack = new Stack<>();

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

        String[] brackets = br.readLine().split("");

        int answer = 0;
        int tmp = 1;

        for (int i = 0; i < brackets.length; i++) {
            String bracket = brackets[i];
            if(bracket.equals("(")) {
                stack.push(bracket);
                tmp *= 2;
            }
            else if(bracket.equals(")")) {
                if(stack.isEmpty() || !stack.peek().equals("(")) {
                    System.out.println(0);
                    return;
                }

                if(brackets[i-1].equals("(")) {
                    answer += tmp;
                }

                stack.pop();
                tmp /= 2;
            }
            else if(bracket.equals("[")) {
                stack.push(bracket);
                tmp *= 3;
            }
            else if(bracket.equals("]")) {
                if(stack.isEmpty() || !stack.peek().equals("[")) {
                    System.out.println(0);
                    return;
                }

                if(brackets[i-1].equals("[")) {
                    answer += tmp;
                }

                stack.pop();
                tmp /= 3;
            } else {
                System.out.println(0);
                return;
            }
        }

        if(!stack.isEmpty()) {
            System.out.println(0);
        } else {
            System.out.println(answer);
        }
    }
}

✏ 설명

쉬워보여서 골랐는데 생각보다 고려해야할 게 너무 많은 문제였다.

나는 이 문제를 분배법칙을 활용하여 해결하였다.
아마 이게 가장 핵심 키워드가 아닐까 싶다.

예를 들어 (()[[]])([]) 이 입력이 들어왔을 때 식으로 변환하면 다음과 같다.
$2*(2+3*3)+2*3$

분배법칙을 사용하여 이 식을 정리하면 다음과 같다.
$2*2+2*3*3+2*3$

이 식을 위의 입력과 연관지어 생각해보면 괄호가 닫힐 때마다 여태까지의 값을 곱하고 더하면 된다.
이렇게 말하면 잘 이해가 안되니 위 입력을 하나씩 뜯어보며 설명하겠다.

각 입력에 대한 동작은 다음과 같다.

• ( 또는 [이 입력되는 경우
  1. 스택에 해당 괄호를 넣고 tmp에 각각 2, 3을 곱해준다.
• )이 입력되는 경우
  1. 스택이 비어있거나, 스택의 맨 위의 값이 (이 아니라면 에러
  2. 에러가 아니라면 맨 위의 값이 (이므로 해당 값을 스택에서 제거한다.
  3. 만약 가장 처음 괄호가 닫힌 경우라면, 즉 이전 값이 (이었다면 answer에 tmp를 더해준다.
  4. 괄호가 닫힐 때마다 /2를 해주어 tmp 값을 정리한다.
• ]이 입력되는 경우
  1. )이 입력되는 경우에서 2를 3으로 변경하는 것 외에 동일하다.