[Stack] 2504번 - 괄호의 값

[백준] 2504번 - 괄호의 값

📝 나의 풀이

이 문제를 보자마자 Stack을 활용해야겠다는 생각이 떠올랐다.

‘()’ 인 괄호열의 값은 2이다.
‘[]’ 인 괄호열의 값은 3이다.
‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

하지만 이 조건을 만족시키는 것을 어떻게 해야할지 막막했다.

이 문제를 쉽게 풀기 위해서 기억해야할 것은 분배법칙이다.

분배 법칙

A*(B+C) = A*B + A*C

스택 연산 과정

answer : 전체 결과 저장하는 변수
value : 현재 괄호의 가중치를 저장하는 변수

1. 열린 괄호인 경우
stack 에 push 한 뒤 임시 변수에 곱 연산을 한다.

2. 닫힌 괄호인 경우    
→ 2.1 이전 괄호가 짝이 맞는 열린 괄호인 경우
더 이상 곱 연산이 적용 되지 않는 원소이므로 최종 결과 값에 더해준다   

→ 2.2 stack의 맨 위 원소와 짝이 맞지 않거나 stack 이 비어 있는 경우
잘못된 괄호이므로 break 

stack 에서 pop 한 뒤 괄호에 맞는 값을 임시 변수에 나누기 연산을 한다.

그냥 이 로직대로 손으로 직접 쓰면서 보면 이해가 간다.

👩🏻‍💻 최종 코드

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		Stack<Character> stack = new Stack<>();
		int answer = 0;
		int value = 1;
		
		for(int i = 0; i < input.length(); i++) {
			char tmp = input.charAt(i);
			
			if(tmp == '(') {
				stack.push(tmp);
				value *= 2;
				continue;
			}
			
			if(tmp == '[') {
				stack.push(tmp);
				value *= 3;
				continue;
			}
			
			if(tmp == ')') {
				if(stack.isEmpty() || stack.peek() != '(') {
					answer = 0;
					break;
				}
				
				if(input.charAt(i-1) == '(') {
					answer += value;
				}
				stack.pop();
				value /= 2;
				continue;
			}
			
			if(tmp == ']') {
				if(stack.isEmpty() || stack.peek() != '[') {
					answer = 0;
					break;
				}
				
				if(input.charAt(i-1) == '[') {
					answer += value;
				}
				stack.pop();
				value /= 3;
			
			}
		}
		
		if(!stack.isEmpty()) System.out.println(0);
		else System.out.println(answer);
	}

}