[BOJ] 2504번 괄호의 값 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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));

        String s = br.readLine();
        Stack<Character> stack = new Stack<>();

        int total = 0;
        int val = 1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '(') {
                stack.push(c);
                val *= 2;
            } else if (c == '[') {
                stack.push(c);
                val *= 3;
            } else if (c == ')') {
                if (stack.isEmpty() || stack.peek() != '(') {
                    total = 0;
                    break;
                }

                if (s.charAt(i - 1) == '(') {
                    total += val;
                }
                stack.pop();
                val /= 2;
            } else if (c == ']') {
                if (stack.isEmpty() || stack.peek() != '[') {
                    total = 0;
                    break;
                }

                if (s.charAt(i - 1) == '[') {
                    total += val;
                }
                stack.pop();
                val /= 3;
            }

        }

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

        System.out.println(total);
    }
}

📄 해설

접근

• 스택을 사용하여 푸는 문제로, 소괄호와 대괄호 두 가지에 대한 케이스를 생각해야해서 까다로웠던 문제
• 여는 괄호를 계속 스택에 넣는 것은 동일하지만, 이 때 추가적인 처리가 필요했었다.
• 값들을 계산하는 기법을 생각해내지 못해서 해결하지 못하고 다른 사람의 풀이를 봤다.

과정

• Character 타입의 스택을 하나 선언하고, 결과 값을 담을 변수 ret 와 임시 계산 값을 담고 있을 변수 val 을 각각 0 과 1로 초기화한다. (val 을 1로 초기화한 이유는 이후 설명)
• 여는 괄호인 경우, 각 괄호에 따라 2 또는 3을 val 에 곱하고, 스택에 여는 괄호를 넣는다. 값을 더하는 것이 아니라 곱셈으로 계산하기 때문에 val 을 1로 초기화한 것
• 닫는 괄호의 경우 두 가지로 나뉜다.
  1. 스택이 비어있거나 스택의 탑이 같은 종류의 괄호가 아닌 경우는 올바른 괄호열이 아니므로 ret 을 0으로 초기화하고 출력한다.
  2. 직전 문자가 같은 종류의 괄호인 경우, ret 에 임시 값인 val 값을 더하고, 스택에서 여는 괄호를 꺼낸다. 그리고 val 값을 괄호에 따라 2 또는 3으로 나눈다.
• 문자열을 전부 순회했음에도 스택이 비어 있지 않은 경우도 올바른 괄호열이 아니므로 ret 을 0으로 초기화한다.
• ret 을 출력한다.