백준 2504번 괄호의 값

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

public class Bracket_Value {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        Stack<Character> stack = new Stack<>();
        boolean flag = true;
        int cnt = 1;
        int answer = 0;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if(c=='('){
                stack.add(c);
                cnt *= 2;

            }
            else if(c=='['){
                stack.add(c);
                cnt *= 3;
            }
            else{
                if(c==')'){
                    if(stack.isEmpty()||stack.peek() == '['){
                        flag = false;
                        break;
                    }
                    if(str.charAt(i-1)=='('){
                        answer += cnt;

                    }
                    stack.pop();
                    cnt/=2;
                }else if(c==']') {
                    if(stack.isEmpty() || stack.peek() != '[') {
                        flag=false;
                        break;
                    }
                    if(str.charAt(i-1)=='[') {
                        answer += cnt;
                    }
                    stack.pop();
                    cnt /= 3;
                }
                else {
                    flag = false;
                    break;
                }
            }
        }
        if(!flag || !stack.isEmpty()) {
            System.out.println(0);
        }else {
            System.out.println(answer);
        }
    }
}

풀이방법

1. 크게 분류하면 괄호가 열렸을때마다 스택에 넣고, 닫힐때마다 하나씩 뺀다.
2. 단, 스택이 비었을때 괄호를 닫거나, [ ), ( ] 일때, for문을 다 돌아도 stack에 괄호가 남아있는 경우를 제외시킨다.
3. 값을 세는것은 (일때 cnt x 2 [ 일때 cnt x 3 해준다. 괄호가 정상적으로 닫히면 answer에 cnt값을 더해준다.
   👉 (()[[]])([])괄호가 있다면 2(2+3 x 3)+2 x 3 이렇게 계산해야 한다.
   하지만 분배법칙을 통해 식을 변환하면 (2 x 2)+(2 x 3 x 3) + (2 x 3) 이렇게 바꿀 수 있다.
4. 괄호가 닫힐때마다 cnt를 닫은괄호의 값으로 나눠준다.

후기

이 풀이는 분배법칙을 생각해야 할 수 있는 풀이여서 안하고 풀이하는 로직을 고민했었는데, 도저히 모르겠다.. 분배법칙을 떠올려서 풀수가 있는건가,, 진짜 절대 못할꺼 같은데