[C++] 백준 2504번 - 괄호의 값

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

2504번: 괄호의 값

 

 

스택의 활용 문제입니다.

처음에 문제에 접근할 때 임시 변수 tmp에 값을 계산하다가 닫는 괄호(')', ']')가 나오면 이를 ans에 더하는 것까지는 생각하였는데, 그 후 tmp를 초기화해버리면 이전 괄호들의 정보가 날아가기 때문에 고민을 많이 했던 문제입니다.

결국 생각보다 구현이 쉽지 않아 삽질을 조금 하다가 검색을 통해 다음 블로그 글을 참고하였습니다.

 

https://mjmjmj98.tistory.com/70

[백준 BOJ / C++] 2504번: 괄호의 값

 

이 문제는 분배법칙을 사용하여 생각보다 간단히 구현할 수 있습니다.

예를 들어 '( ( ) [ [ ] ] )'의 경우에 2 x ( 2 + 3 * (3) )으로 계산되는데,

이는 분배 법칙을 적용했을 때 (2 * 2) + (2 * 3 * (3))와 같습니다.

 

문제는 위에서 더해지는 식 (2 * 2), (2 * 3 * 3)을 어떻게 만드느냐인데, 이때 tmp 변수를 사용합니다.

 

tmp 변수를 1로 초기화하고, '('와 '['가 나온다면 괄호를 스택에 넣고 tmp에 각각 2, 3을 곱해줍니다.

진행하면서 닫는 괄호 ')', ']'가 나온다면 이전 괄호가 각각 '(', '['인지 확인하고, 현재 보고 있는 괄호가 '()'와  '[]'의 닫는 괄호일 경우, (즉, '( ( ) [ [ ] ] )' 인 경우) 현재 계산하고 있던 tmp값을 ans에 더하고 값을 괄호에 따라 2, 3으로 나누어주고 스택을 pop 합니다

이 외 경우의 닫는 괄호일 경우 (즉, '( ( ) [ [ ] ] ) '인 경우) 에는 tmp 변수의 값을 각각 2, 3으로 나누고 스택을 pop 하고, ans에는 값을 더하지 않습니다.

 

'( ( ) [ [ ] ] )' : tmp = 2, ans = 0

'( ( ) [ [ ] ] )' : tmp = 2 * 2, ans = 0

'( ( ) [ [ ] ] )' : tmp = 2, ans = 2 * 2     (ans값에 더하기)

'( ( ) [ [ ] ] )' : tmp = 2 * 3, ans = 2 * 2

'( ( ) [ [ ] ] )' : tmp = 2 * 3 * 3, ans = 2 * 2

'( ( ) [ [ ] ] )' : tmp = 2 * 3, ans = (2 * 2) + (2 * 3 * 3)     (ans값에 더하기)

'( ( ) [ [ ] ] )' : tmp = 2, ans = (2 * 2) + (2 * 3 * 3)

'( ( ) [ [ ] ] )' : tmp = 1, ans = (2 * 2) + (2 * 3 * 3)

 

ans = 22

 

이 외에 닫는 괄호가 나왔는데 스택이 비어있거나, 괄호의 짝이 맞지 않거나 반복문을 빠져나왔는데 스택에 값이 남아있는 경우(여는 괄호가 더 많은 경우)에는 올바르지 못한 괄호열이기 때문에 ans에 0을 넣어 출력합니다.

 

#include<iostream>
#include<stack>
using namespace std;

string str;
stack<char> s;
int ans;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> str;
	int tmp = 1;
	char pre = ' ';
	for (int i = 0; i < str.size(); i++)
	{
		if (str[i] == '(' || str[i] == '[')
		{
			s.push(str[i]);
			if (str[i] == '(')
				tmp *= 2;
			else
				tmp *= 3;
		}
		else
		{
			if (str[i] == ')')
			{
				if (s.empty()) {
					ans = 0;
					break;
				}
				if (s.top()=='[') {
					ans = 0;
					break;
				}
				s.pop();

				if (pre == '(')	//ans에 값을 더해야 한다
				{
					ans += tmp;
					tmp /= 2;
				}
				else
					//이미 값이 더해져 있음
				{
					tmp /= 2;
				}
			}
			else
			{
				if (s.empty()) {
					ans = 0;
					break;
				}
				if (s.top() == '(') {
					ans = 0;
					break;
				}
				s.pop();

				if (pre == '[')
				{
					ans += tmp;
					tmp /= 3;
				}
				else
					tmp /= 3;
			}
		}
		pre = str[i];
	}

	if (!s.empty())
		ans = 0;

	cout << ans;

	return 0;
}