[백준] 2504 괄호의 값

 

2504번: 괄호의 값 (acmicpc.net)

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 이다.

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

 

 

내풀이

이 문제를 다 읽자마자 들은 생각이 무엇인가?

=> 괄호 문제다 => 스택 쓰면 되겠는데? 

=> 근데 기초적인 문제와 다르게 값을 정해진 규칙에 따라 계산하여야 하는 부분이 존재했다. 

그리고 이 부분을 해결하려면 재귀를 사용하여 괄호를 단계별로 계산하면 좋겠다 라는 아이디어로 시작했다.

 

그 결과물인데... 재귀 부분에서 생각이 꼬여서 구현하는 시간도 오래 걸렸는데, 백준에서 시간 초과가 나서 아예 갈아 엎었다.

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

public class Main{
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static String src = "(()[[]])([])";
	
	static int index,result;
	static boolean flag;
	static char[] data;
	static Stack<Character> stack;
	public static void main(String arg[]) throws IOException {
		//input= new BufferedReader(new InputStreamReader(System.in));
		input= new BufferedReader(new StringReader(src));

		data = input.readLine().toCharArray();

		//System.out.println(Arrays.toString(data));

		stack = new Stack<>();
		index = 0;
		result = 0;

		while (index < data.length) {
			if (flag) {
				result = 0;
				break;
			}
			result += bracket();
		}
		System.out.println(result);
	}

	//한꺼풀씩
	public static int bracket() {
		int temp = 0;
		//System.out.println("재귀"+index +" "+data[index]);
		if (data[index] == '(' || data[index] == '[') {
			stack.push(data[index]);
			index++;
		}

		//스택이 빌 때까지 반복
		while (!stack.isEmpty()) {
			//이어지는 () or []
			if (data[index] == '(' || data[index] == '[') {
				temp += bracket(); //안의 괄호 값 재귀해서 구함

			}// () 이 완성될 때 2
			else if (stack.peek() == '(' && data[index] == ')') {
				stack.pop();
				index++;
				if (temp == 0) {
					temp = 1;
				}
				return 2 * temp;

			} // [] 이 완성될 때 3
			else if (stack.peek() == '[' && data[index] == ']') {
				stack.pop();
				index++;
				if (temp == 0) {
					temp = 1;
				}
				return 3 * temp;
			} //올바르지 않은 입력인 경우
			else{
				flag = true;
				return 0;
			}
		}

		return temp;
	}
}

 

반복문과 스택을 이용하여 해결하는 방법으로 해결했다.

( ( ) [ [ ] ] ) 으로 예를 들면 

( 에서 temp *= 2 로 2가 되고 

이어지는 ( 에 temp *= 2 로 4가 되고 이것은 이어지는 ) 로 닫히면서 result에 4를 더해주고 temp /= 2 로 ( ) 를 처리하기 전으로 돌아온다 즉 여기까지가 ( ( ) ) 를 처리한 것이다

이어지는 [ [ ] ] 에선 temp *= 3 을 두번하고 2 * 3 * 3 을 result 에 더해주고 두 번째 ] 에서는 바로 앞 문자가 [ 이 아니기에 result 에 값을 더하지 않음으로서 정확한 값을 result 에 더해준다.

이 외의 불가능한 경우의 수를 쳐내는 경우를 넣어 해결하였다.

 

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

public class Main{
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static String src = "(()[[]])([])";
	
	static int result;
	static boolean flag;
	static char[] data;
	static Stack<Character> stack;
	public static void main(String arg[]) throws IOException {
		//input= new BufferedReader(new InputStreamReader(System.in));
		input= new BufferedReader(new StringReader(src));

		data = input.readLine().toCharArray();

		//System.out.println(Arrays.toString(data));

		stack = new Stack<>();
		result = 0;
		int temp = 1;

		for (int i = 0; i < data.length; i++) {
			// 입력이 (,[ 인 경우
			if (data[i] == '(') {
				temp *= 2;
				stack.add('(');
			} else if (data[i] == '[') {
				temp *= 3;
				stack.add('[');
			}
			//불가능한 경우
			else if (data[i] == ')' && (stack.empty() || stack.peek() != '(')) {
				flag = true; //불가능한 경우 저장할 boolean 체크하고 break 으로 탈출
				break;
			} else if (data[i] == ']' && (stack.empty() || stack.peek() != '[')) {
				flag = true;
				break;
			}
			// ), ] 으로 마무리되는 경우
			else if (data[i] == ')') {
				if (data[i - 1] == '(') { //바로 앞이 ( 이였다면
					result += temp; // 2를 곱했던 값 result에 더하고
				}
				stack.pop(); // 스택에서 ( 꺼낸후 
				temp /= 2; // temp/2 해줌   
			} //위의 ] 버전
			else if (data[i] == ']') {
				if (data[i - 1] == '[') {
					result += temp;
				}
				stack.pop();
				temp /= 3;
			}
		}

		if (flag || !stack.empty()) { //불가능한 경우이거나 stack을 다 안비운 경우
			System.out.println(0); 
		} else {
			System.out.println(result);
		}
	}
}