[백준 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 이다.

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

 

입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

 

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다. 

---

접근

문제에서 주어진대로 규칙을 찾으려고 했다. 그런데 코드가 너무 복잡해지고 길어졌으며 예외 케이스가 많이 발견되었다. 

따라서 하나로만 접근하는 것이 아니라 다양한 관점에서 접근하는 것이 중요해졌고 이런 유형의 문제는 규칙을 빠르게 찾는 것이 중요하다.

 

규칙은 다음과 같다.

- "("가 나온다면 1로 초기화된 flag에 2를 곱하고 "["가 나온다면 3을 곱하고 push한다.

- 닫는 괄호가 나오고 이전 인덱스와 짝이 맞을 경우 최종해에 더한다.

- 닫는 괄호가 나온다면 괄호의 종류에 따라 flag를 2 또는 3으로 나누고 스택을 pop한다.

 

구현

위에서 찾은 규칙을 적용한 것이다.

여기에 괄호의 짝이 맞지 않는 경우도 있을 수 있기 때문에 닫는 괄호가 나왔을 때 스택이 비어있거나 스택의 top과 짝이 맞지 않을경우 최종해인 answer에 0을 대입하고 탐색을 종료한다.

#include<iostream>
#include<algorithm>
#include<stack>
#include<string>
#include<cstring>
using namespace std;


int main()
{
	string str;
	cin >> str;

	stack<char> st;
	int flag = 1;
	int answer = 0;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == '(') {
			flag *= 2;
			st.push(str[i]);
		}
		else if (str[i] == '[') {
			flag *= 3;
			st.push(str[i]);
		}
		else if (str[i] == ')') {
			if (st.empty() || st.top() != '(') {
				answer = 0;
				break;
			}
			
			if (str[i - 1] == '(')
				answer += flag;
			flag /= 2;
			st.pop();
			
		}
		else if (str[i] == ']') {
			if (st.empty() || st.top() != '[') {
				answer = 0;
				break;
			}
			
			if (str[i - 1] == '[')
				answer += flag;
			flag /= 3;
			st.pop();
			
		}

	}
	if (!st.empty())
		answer = 0;
	cout << answer << endl;
	return 0;
}