[문제] BOJ 2504. 괄호의 값
문제 링크 :
https://www.acmicpc.net/problem/2504

접근 방법 및 풀이

• 일단 분배 법칙을 바로 떠올렸다면 풀어볼만한 문제다.
• 스택을 이용해서 풀었고, 올바른 괄호열인지 아닌지 체크하는건 어렵지 않아서 올바른 괄호열이 아니라면 0을 출력하는 것 까진 접근했다. 이후는 숫자 계산의 문제다.
• 예를 들면, ()()는 2 + 2 이고, (())는 2 * 2 이다. 여기까진 쉽다.
• ( ( ) [ ] ) 라면, 이걸 숫자로 대입하면 2 * (2 + 3) 이렇게 풀이가 된다. 그리고 이걸 분배법칙을 적용해서 식을 풀면, 2 * 2 + 2 * 3이다.
• 마찬가지로 예제 1번의 ( ( ) [ [ ] ] ) 이 부분을 숫자로 대입하면, 2 (2 + 3 3)이 되고, 분배법칙을 적용해서 식을 풀면 4 + 6 * 3 = 4 + 18 = 22가 된다.
• 이걸 생각하고 코드를 작성하면 되는데, 가장 먼저 arr[ ] 문자 배열에 입력을 받고 길이만큼 탐색한다.
• 문자가 '('나 '[' 일 경우는 스택에 push하고 tmp에 '('일경우는 2를 곱하고 '['일경우는 3을 곱한다.
• 문자가 ')' 나 ']' 일 경우엔 올바른 괄호열인지 체크하고, answer에 multiplier를 더해주고 다시 ')'나 ']'에 맞춰 2 또는 3으로 multiplier를 다시 나눠준다.
• 근데 이때, 그냥 무조건 answer에 multiplier를 더해주는게 아니라, 입력받은 arr[ ] 배열에서 현재 i 바로 전 i-1의 문자가 여는 괄호일 경우에만 더해줘야 한다.
• 예를 들면, arr[ ] 이 다음과 같을 경우에는

i	0	1	2	3	4	5
arr[i]	[	[	[	]	]	]
multiplier	3	9	27	9	3	1

• i가 3인 순간에 닫는 괄호를 만나 지금까지의 multiplier를 answer에 더할 것이다. 그럼 answer는 27이되고 더이상 answer에 값이 더해지면 안된다. 이때 더해지는 순간은 i-1인 arr[2]가 여는 괄호일때만 지금까지 곱한 값을 더해주는 것이다.
• i가 4인 순간 또 닫는 괄호를 만나서 multiplier인 9를 더하는게 아니라, arr[3]이 여는 괄호가 아니기 때문에 더해줄 필요없이 multiplier를 나눠주기만 하면 된다.
• answer가 0이 나올 때에는 무조건 for문을 탈출하도록 break loop를 해주면 된다.

JAVA 코드

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

public class Main {
    public int solution(String str) {
        int answer = 0;
        int multiplier = 1;
        Stack<Character> stack = new Stack<>();

        int length = str.length();

        // 분배 법칙을 생각하자!
        loop:
        for (int i = 0; i < length; i++) {
            switch (str.charAt(i)) {
                case '(':
                    stack.push(str.charAt(i));
                    multiplier *= 2;
                    break;
                case ')':
                    if (stack.isEmpty() || stack.peek() != '(') {
                        answer = 0;
                        break loop;
                    }

                    if (str.charAt(i - 1) == '(') {
                        answer += multiplier;
                    }
                    stack.pop();
                    multiplier /= 2;
                    break;
                case '[':
                    stack.push(str.charAt(i));
                    multiplier *= 3;
                    break;
                case ']':
                    if (stack.isEmpty() || stack.peek() != '[') {
                        answer = 0;
                        break loop;
                    }

                    if (str.charAt(i - 1) == '[') {
                        answer += multiplier;
                    }
                    stack.pop();
                    multiplier /= 3;
                    break;
            }
        }
        
        if (stack.isEmpty()) {
            answer = 0;
        }

        return answer;
    }

    public static void main(String[] args) throws IOException {
        Main main = new Main();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str = br.readLine();

        System.out.println(main.solution(str));
    }
}

후기

골드 5 문제인데 골드 1 정도는 되어야 하지 않을까 하는 생각이 들 정ㄷ로 충격받은 문제다. 이런 문제가 코테에 나오면 끔찍할 것 같다. 생각하는데 너무 시간이 오래 걸
렸고, 한번만에 풀지 못해서 인터넷에 찾았다. 그리고 그걸 이해하는데도 시간이 오래 걸렸다ㅠㅠ
분기가 많으니까 올바른 괄호열인지 잘 확인해야 하고, multiplier가 더해지는 순간과 아닌 순간을 잘 나누어야 한다.
이걸 이해 못해서 무려..3시간이나 썼다. 부끄럽지만, 이해했으니까 다음에 비슷한 문제가 나오면 이렇게 접근해서 풀어봐야겠다.
참고로 다른 문제 풀이들을 보면 for문을 빠져나오도록 레이블을 달고 조건을 미충족하면 바로 탈출하도록 하지 않아서 채점하면 틀린 것으로 나온다. 이건 한 유저가 반례인 ()]()를 제시했기 때문에 데이터셋이 추가되었기 때문이다.
그래서 위의 코드로 푸는 것을 추천한다!