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

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

---

문제

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

public class Main {

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

		Stack<Character> st = new Stack<>();
		boolean flag = true; 
		int answer = 0;
		int cnt =1;
		for(int i=0; i<line.length(); i++) {
			char cur = line.charAt(i);
			if(cur == '(') {
				st.push(cur);
				cnt *= 2;
			}
			else if(cur == '[') {
				st.push(cur);
				cnt *= 3;
			}
			else {
				if(cur == ')') {
					if(st.isEmpty() || st.peek() != '(') {
						flag=false;
						break;
					}
					if(line.charAt(i-1) =='(') {
						answer += cnt;
					}
					st.pop();
					cnt /= 2;
				}else if(cur==']') {
					if(st.isEmpty() || st.peek() != '[') {
						flag=false;
						break;
					}
					if(line.charAt(i-1)=='[') {
						answer += cnt;
					}
					st.pop();
					cnt /= 3;
				}
				else {
					flag = false;
					break;
				}
			}
		}
		if(!flag || !st.isEmpty()) {
			System.out.println(0);
		}else {
			System.out.println(answer);
		}
	}
}

 

코드를 구현할 수 있는 능력도 필요하지만, 결과적으론 컴퓨터로 구현하기 전에 아이디어를 떠올리는 것이 먼저임을 확실히 느낀 문제이다.

 

괄호 문제를 만난 순간부터 큐 혹은 스택을 사용해야 한다는 것은 어느 정도 느낌이 왔다. 다만 거기까지였다...

문제를 차근히 분석해보자.

(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3 ×3=11 이므로 ‘(()[[]])’의 괄호값은 2 ×11=22이다. 그리고 ‘([])’의 값은 2 ×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28이다.
문제에서 제시해 준 풀이임과 동시에 상당히 현혹되어 헷갈릴 수 있는 설명이다.

 

아이디어 -> 코딩도 좋지만 코딩-> 아이디어라는 순서도 고려해 보자

우리는 ) 혹은 ]를 만날 때마다 계산을 진행하거나 어떠한 연산이 들어가야 된다는 것을 알고 있다.

그럼 순서대로 진행해 보자.

1. (가 나왔다. 이 친구는 2라는 숫자가 되어줄지 x2가 되어줄지 모른다. 일단 보류하자.

2. (가 다시 나왔다. 여기서 알 수 있다. 아 이전의 (는 반드시 x2가 되어주겠다는 거구나. 그리고 난 아직 모르는구나.

3. )가 나왔다. 그렇다면 2번의 (와 붙어 2라는 숫자가 되어줄 것이고 1번의 (는 아직 유효하다! 즉 나의 현재 식은 2x(2+ 정도겠구나

4. [가 나왔다. 이 친구는 3이라는 숫자가 되어줄지 x3이 되어줄지 모른다. 일단 보류하자.

5. [가 다시 나왔다. 여기서 알 수 있다. 아 이전의 [는 반드시 x3이 되어주겠다는거구나. 그리고 난 아직 모르는구나.

6. ]가 나왔다. 5번의 [는 3이 되어주겠다는 것이다. 이쯤에서 식을 다시 정리해 보자. 2x(2+3x(3+가 된다.

7. ]가 나왔다. 여기선 4의 [가 마무리된다. 2x(2+3x3 이 된 것이다.

8. )가 나왔다. 1번의 (가 마무리 된 것이다. 2x(2+3x3)

 

자 이렇게 봐도 헷갈릴 수 있다. 여기서 왜 코딩->아이디어라는 것을 떠올렸냐면 2x( 이런 식으로 묶는 것은 지극히 내가 수학을 하는 시점이다. 컴퓨터라면 2x2 + 2x3x3이 더욱 편할 수도 있다는 것이다!

 

정리하자면.

1이 기본이라는 전제하에

(를 만나면 무조건 x2가 들어간다.

[을 만나면 무조건 x3이 들어간다.

)를 만나면 동작을 취한다. 일단 유효한지 검사하고 유효하다면, 이 전의 인덱스가(인 경우 총값에 더한다. 문제를 보면 x2x2가 되어 4가 정상적으로 더해지는 것을 볼 수 있다. 이후 /2를 해준다. 왜냐면 x2가 하나는 마무리되기 때문이다.

]를 만나도 유사한 동작을 한다. x2 x2에서 x2 x2/ 2가 되어 x2 만 남았고 여기에 x2 x3 x3이 되어 옳은 값이 들어가는 것을 확인할 수 있다.

 

이러한 문제는 개인적으로 답지를 보고 숙달하는 방법이 제일 현명하다고 생각한다. 확실하게 체크해 두고 주기적으로 확인하며 내 것으로 만들어야 할 것 같다.