[백준] 2504 괄호의 값

문제

---

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. 
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. 

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

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다. 

 

 

 

 

풀이

---

Stack을 이용해서 문제를 풀었다.

 

올바르지 않은 괄효열의 조건은 두가지다.

1. 괄호의 짝이 맞지않는 경우
2. 괄호가 갯수가 짝수개가 아닌경우

우선 이두가지를 구분해 주어야한다. 스택을 이용해서 가장 나중에 들어온 열린괄호와 닫힌괄호가 짝이 맞지않는지 판단을 해주었다.

else if(me.charAt(i) == ')') {
	if(stack.isEmpty() || stack.pop() != '(') {
		answer = 0;
		break;
	}
}
else if(me.charAt(i) == ']') {
	if(stack.isEmpty() || stack.pop() != '[') {
		answer = 0;
		break;
	}
}

위와 같이 판단을 해주었다.

 

그리고 괄호의 갯수가 홀수인 경우는 남는 괄호가 있는지를 판단하여 주었다.

if(!stack.isEmpty())
	answer = 0;

 

이제 문제를 계산해주는 알고리즘이 필요한데,

 

문제예시를 보며 풀어보면

(()[[]])([]) 의 경우

 

 ( () [[]] ) 이것을 (xy) 의 경우에 따라 나눠줄 수 있다.

(()) + ([[]]) 의 값과 동일하게 표현할 수 있다. 이점을 고려하면 ( 일때는 *2 를 해주고 [ 일때는 * 3 을해준다.

) 이 나오면 /2 를  ]이 나오면 / 3 을 해주어 값을 다시 롤백하고 그때의 값을 더해준다.

 

하지만 이때 주의 할점이 있다. 

 

(()) 의 경우 ) 에서 값을 더해주게 되면 2번을 더하게 된다. 따라서 값을 더해주었는지를 체크해주어야 한다.

 

위의 방식에 맞게 풀어주면 된다.

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

public class Main {	

	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		String me = bufferedReader.readLine();
		
		Stack<Character> stack = new Stack<>();
		int answer = 0;
		boolean inout = false;
		int sum = 1;
		for(int i = 0 ; i < me.length(); i++) {
			if(me.charAt(i) == '(') {
				stack.add(me.charAt(i));
				sum *= 2;
				inout = true;
			}
			
			else if(me.charAt(i) =='[') {
				stack.add(me.charAt(i));
				sum *= 3;
				inout = true;
			}
			
			else if(me.charAt(i) == ')') {
				if(stack.isEmpty() || stack.pop() != '(') {
					answer = 0;
					break;
				}
				if(inout) {
					answer += sum;
				}
				sum /= 2;
				inout = false;
				
			}
			
			else if(me.charAt(i) == ']') {
				if(stack.isEmpty() || stack.pop() != '[') {
					answer = 0;
					break;
				}
				if(inout) {
					answer += sum;
				}				
				sum /= 3;
				inout = false;
			}
		}
		
		if(!stack.isEmpty())
			answer = 0;
		
		System.out.println(answer);
	}
	
}