[BOJ] 2504: 괄호의 값 (JAVA)

문제

https://www.acmicpc.net/problem/2504

 

여담

덧셈과 곱셈을 어떻게 나눠서 계산할지 몰라서 결국 풀이를 참고했다. 처음에는 이해가 안 돼서 계속 써보다가 분배법칙을 이용하면 된다는 말을 보고 이해했다..

 

다시 풀 때도 풀이 로직을 알아서 쉽게 풀었지, 몰랐다면 끝까지 못 풀었을 것 같다. 다들 어떻게 이런 생각을 하는 걸까? 진짜 대단하다. 나도 분발해야지..

 

풀이

이 문제는 괄호를 기반으로 값을 구하는 것이기 때문에 스택을 이용해서 문제를 풀면 된다.

 

풀이 과정은 다음과 같으며, 자세한 내용은 코드를 참고하면 된다. 수학의 분배법칙을 생각하면 풀이 흐름을 쉽게 이해할 수 있을 것이다. (2 × (2 + 3 × 3) = (2 × 2) + (2 × 3 × 3)) 

1. ( 또는 [를 만나는 경우
   • 스택에 괄호를 넣고, 괄호의 값을 `total`에 곱해준다. ((는 2, [는 3)
     • stack.push(now)
     • total *= 2 또는 total *= 3
2. )를 만나는 경우
   • 스택이 비어있거나 stack.peek가 (이 아닌 경우
     • 올바르지 못한 문자열이므로 0을 출력하고 종료하기
   • 바로 이전 괄호가 (인 경우
     • 가장 안쪽 괄호, 즉 해당 연산의 끝을 뜻하므로 이때까지 저장해놓은 total 값을 answer에 더하기
   • 괄호를 닫을 때마다 스택에서 pop하고 저장한 값들을 정리하기
     • stack.pop()
     • total /= 2
3. ]를 만나는 경우
   • 스택이 비어있거나 stack.peek가 [이 아닌 경우
     • 올바르지 못한 문자열이므로 0을 출력하고 종료하기
   • 바로 이전 괄호가 [인 경우
     • 가장 안쪽 괄호, 즉 해당 연산의 끝을 뜻하므로 이때까지 저장해놓은 total 값을 answer에 더하기
   • 괄호를 닫을 때마다 스택에서 pop하고 저장한 값들을 정리하기
     • stack.pop()
     • total /= 3

 

코드

import java.util.*;
import java.io.*;

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

        int answer = 0, total = 1;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            char now = str.charAt(i);
            // 왼쪽 괄호면 스택에 push & total에 괄호 값 곱하기
            if (now == '(') {
                stack.push(now);
                total *= 2;
            } else if (now == '[') {
                stack.push(now);
                total *= 3;
            } else if (now == ')') {
                // ')'의 짝인 '('가 없으면 입력이 올바르지 못한 괄호열
                if (stack.isEmpty() || stack.peek() != '(') {
                    System.out.println(0);
                    return;
                }
                // 짝이 맞는 괄호가 연속해서 있다면 더할 차례
                if (str.charAt(i - 1) == '(') {
                    answer += total;
                }
                total /= 2;
                stack.pop();
            } else if (now == ']') {
                // ']'의 짝인 '['가 없으면 입력이 올바르지 못한 문자열
                if (stack.isEmpty() || stack.peek() != '[') {
                    System.out.println(0);
                    return;
                }
                if (str.charAt(i - 1) == '[') {
                    answer += total;
                }
                total /= 3;
                stack.pop();
            }
        }
        if (stack.isEmpty()) System.out.println(answer);
        else System.out.println(0);
    }
}

---

참고

https://loosie.tistory.com/349