백준 [2504] 괄호의 값 (JAVA)

문제

풀이

분배 법칙 힌트를 얻고 풀어보려 했지만 내가 닫는 괄호가 여러 개 나올 때에 처리가 애매하여 풀이를 참고했다.

 

1. 여는 괄호에 대해서는 괄호열 값에 따라 바로 곱셈 법칙을 적용하여 tmp값에 저장한다.
2. 처음 닫는 괄호열이 나왔을 때
3. 스택이 비어있거나 peek 값이 여는 괄호가 아니라면 올바른 괄호열이 아님.
4. 바로 이전의 값(입력받은 괄호열 중 이전의 값. 스택에 있는 값이 아니다.)이 여는 괄호라면 현재까지 tmp에 저장한 값을 ans 변수에 더해준다. (이 값이 분배 법칙에 의해 계산된 값이 된다.)
5. 스택에서 값을 빼고 곱한 괄호열 값을 나눠서 원복 시킨다.
6. () 괄호열과 [] 괄호열 동일하게 적용해준다.
7. 올바른 괄호열이 아니거나 스택에 괄호열이 남아있으면 0을 출력, 그렇지 않으면 결과 값(ans)을 출력

정답코드

package com.baekjoon.data_structure.p2504;

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

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

        String brackets = br.readLine();

        Stack<Character> stk = new Stack<>();

        int res = 0;
        int tmp = 1;
        boolean isCorrect = true;

        for (int i = 0; i < brackets.length(); i++) {
            char now = brackets.charAt(i);

            if (now == '(') {
                stk.push(now);
                tmp *= 2;
            } else if (now == '[') {
                stk.push(now);
                tmp *= 3;
            } else {
                if (now == ')') {
                    if (stk.isEmpty() || stk.peek() != '(') {
                        isCorrect = false;
                        break;
                    }
                    /*
                     * 여기 부분을 이해하지 못함.
                     * 열린 괄호까지 계속해서 연산을 해준다음 처음 만나는 여는 괄호가 올바르면
                     * 그 때까지의 연산을 더해주면 그 이후 닫는 괄호에 대해서는
                     * 스택의 여는 괄호를 빼주고 분배법칙 연산한 값을 원복 시키는 역할을 해야한다.
                     * [] 괄호 역시 똑같이 적용
                     */
                    if (brackets.charAt(i - 1) == '(') {
                        res += tmp;
                    }
                    stk.pop();
                    tmp /= 2;
                } else if (now == ']') {
                    if (stk.isEmpty() || stk.peek() != '[') {
                        isCorrect = false;
                        break;
                    }
                    if (brackets.charAt(i - 1) == '[') {
                        res += tmp;
                    }
                    stk.pop();
                    tmp /= 3;
                }
            }
        }

        if (!isCorrect || !stk.isEmpty()) {
            System.out.println(0);
        } else {
            System.out.println(res);
        }

    }
}