[백준 2504번] 괄호의 값

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

 

다시 풀 문제

문제를 처음 봤을 땐 딱봐도 Stack을 사용해야하는 문제라고 생각했지만, 괄호간의 연산에 대해서 덧셈과 곱셈을 어떻게 처리해야할지 고민했던 문제. 다른 사람의 풀이를 참고하여 풀었다.

 

각각의 case에 대해 경우의 수를 나눠서 backTracking 같이 풀이를 진행하였다. 나는 괄호가 끝날 때, 연산을 진행하려고 했는데, 작성자는 시작하는 괄호가 나왔을 때, 임시로 값을 담아놓고, 만약 괄호가 정상적으로 종료된다면 해당 값을 최종 결과에 저장하는 방식을 사용했다.

따라서 만약 시작하는 괄호가 여러 개 나온다면 계속 tmp에 괄호에 해당하는 연산을 곱해주고, 이후 하나의 괄호가 닫힐 때마다, tmp를 해당 값만큼 나눠준다.

 

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

public class BOJ_G5_2504_괄호의값 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String str = br.readLine();

		Stack<Character> stk = new Stack<>();
		int res = 0;
		int val = 1;

		for (int i = 0; i < str.length(); i++) {
			char curr = str.charAt(i);

			if (curr == '(') {
				stk.push(curr);
				val *= 2;
			} else if (curr == '[') {
				stk.push(curr);
				val *= 3;
			} else if (curr == ')') {
				if (stk.isEmpty() || stk.peek() != '(') {
					res = 0;
					break;
				} else if (str.charAt(i - 1) == '(') {
					res += val;
				}
				stk.pop();
				val /= 2;
			} else if (str.charAt(i) == ']'){
				if (stk.isEmpty() || stk.peek() != '[') {
					res = 0;
					break;
				} else if (str.charAt(i - 1) == '[') {
					res += val;
				}
				stk.pop();
				val /= 3;
			}
		}

		if (!stk.isEmpty()) res = 0;

		sb.append(res);
		System.out.println(sb);
	}
}