[ 백준 2504 ] 괄호의 값 - Stack

 

1. 문제: https://www.acmicpc.net/problem/2504

2504번: 괄호의 값

2. 풀이

Stack을 응용한 대표적인 문제를 꼽으라면 단연 괄호와 관련된 문제라고 할 수 있다.

 

괄호의 쌍이 올바르게 되어 있는가를 판단할 때 스택의 특성을 가장 적극적으로 활용할 수 있는데, 여는 괄호는 스택에 넣고 닫는 괄호는 스택에서 pop을 해 쌍을 확인함으로써 풀이할 수 있다. 문제 해석에 앞서 잠시 올바른 괄호의 쌍인가를 확인하는 코드를 정리하고 간다.

// '()' 소괄호만 있는 경우
public boolean isValid(String str) {
	String arr[] = str.split("");
    boolean ret = true;
    //짝이 맞아야 하는 괄호가 홀 수 개라면 더 이상 볼필요도 없다.
    if(arr.length % 2 == 1)
    	return ret = false;
    
    Stack<String> stack = new Stack<String>();
    for(int i = 0; i < arr.length; i++) {
    	//여는 괄호는 Stack에 Push
    	if(arr[i].equals("(")){
        	stack.push(arr[i]);
        } else {
        	//끄잡아내서 쌍이 맞는지 확인해야되는데 없으면 False
        	if(stack.isEmpty())
            	return ret = false;
            String tmp = stack.pop();
            //괄호의 종류가 여러개일 경우 아래 equals안에 맞는 쌍인지를 확인해줘야함
            //if(!tmp.equals("(")
            //	return ret = false;
        }
    }
    return ret;
}

 

해당 문제는 여기서 한 번 더 꼬아놓았다고 볼 수 있다.

괄호의 쌍이 올바르지 않다면 0을 출력하고 그렇지 않을 경우에 연산을 해야하는데, 이 부분을 어떻게 풀이할지는 다소 고민이 든다.

하지만 천천히 연산을 진행해보면 '사칙연산의 결합법칙'을 통해 풀 수 있음을 볼 수 있다.

 

* 문제의 조건

• X를 올바른 괄호쌍이라고 가정
• () = 2
• [] = 3
• (X) = 2 * 값(X)
• [X] = 3 * 값(X)

 

문제의 예제인 '( ( ) [ [ ] ] ) ( [ ] )'와 같은 쌍이 있다고 생각해보자

연산은 아래와 같을 것이다.

( ( ) [ [ ] ] ) ( [ ] )
= 2 * ( 2 + 3 * ( 3 ) ) + 2 * ( 3 )
= 28 

 

이 때, 이리저리 결합되어 있는 연산들을 완전 풀어헤쳐 보자.

2 * ( 2 + 3 * ( 3 ) ) + 2 * ( 3 )
= ( 2 * 2 ) + ( 2 * 3 * 3 ) + ( 2 * 3 )

 

왜 이 짓을 했는지 전혀 감이 잡히지 않을 수도 있다.

그렇다면 여는 괄호는 각 괄호의 종류에 맞는 곱셈 연산, 닫는 괄호는 나눗셈 혹은 덧셈으로 생각해보면 조금 이해가 될 수 있다. 

 

곱셈을 위한 임시변수(tmp)를 1로 두고 천천히 디버깅을 해보면 다음과 같다.

예제 ( [ ( ) ] [ ] )  // tmp = 1, ans = 0

① (
tmp *= 2   // tmp = 2

② ( [
tmp *= 3   // tmp = 2 * 3

③ ( [ (
tmp *= 2   // tmp = 2 * 3 * 2

④ ( [ ( )
ans += tmp   // ans = 0 + 2*3*2
tmp /= 2   // tmp = 2 * 3

⑤ ( [ ( ) ]
tmp /= 3   // tmp = 2

⑥ ( [ ( ) ] [
tmp *= 3   // tmp = 2 * 3

⑦ ( [ ( ) ] [ ]
ans += tmp   // ans = 0 + 2*3*2 + 2*3
tmp /= 3    // tmp  = 2

⑧ ( [ ( ) ] [ ] )
tmp /= 2   // tmp = 1

 

자세히 보면 닫는 괄호는 항상 해당하는 수로 나눠주고, 바로 이전이 자신의 쌍으로 여는 괄호라면 더하기 처리를 해준다. 이 부분이 이해가 되었다면 코드로 구현하는 것은 어렵지 않다.

 

 

3. 코드

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

public class ValueOfBracket2504 {
	
	static int solve(String str) {
		int ret = 0;
		String arr[] = str.split("");
		if(arr.length % 2 == 1)
			return ret;
		
		Stack<String> stack = new Stack<String>();
		int tmp = 1;
		for(int i = 0; i<arr.length; i++) {
			if(arr[i].equals("(")) {
				tmp *= 2;
				stack.push(arr[i]);
			} else if(arr[i].equals("[")) { 
				tmp *= 3;
				stack.push(arr[i]);
			} else if(arr[i].equals(")")) {
				if(stack.isEmpty() || !stack.peek().equals("("))
					return ret = 0;
				if(arr[i-1].equals("("))
					ret += tmp;
				stack.pop();
				tmp /= 2;
			} else if(arr[i].equals("]")) {
				if(stack.isEmpty() || !stack.peek().equals("["))
					return ret = 0;
				if(arr[i-1].equals("["))
					ret += tmp;
				stack.pop();
				tmp /= 3;
			}
		}
		
		return ret;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String str = br.readLine();
		bw.write(solve(str) + "");
		bw.flush();
		bw.close();
		br.close();
	}

}