C++ [괄호의 값_백준] / #stack #자료구조 #분배법칙

Problem

---

 

괄호의 값_백준

2504번: 괄호의 값

 

간단하게 stack을 이용하여 올바른 괄호열을 구분한 뒤 결과값을 출력하는 문제인줄 알았다. 하지만 문제 정의대로 코드를 짜나가다보니 그냥 해결되는 문제는 아니었다.

 

문제에서 정의된대로

1. () 괄호값은 2

2. [] 괄호값은 3

3. (x) 의 괄호값은 2 * x

4. [x] 의 괄호값은 3 * x

5. xy의 괄호값은 x + y

 

Solve

---

주어진 문자열이 " (()[[]]) "일 경우 결과 값은 (2+3*3)*2 가 된다. 여기서 가장 바깥의 괄호의 2값이 안쪽에 존재하는 괄호값들에 분배되어 곱해진다고 생각하여 풀이하였다.

즉, (2+3*3)*2 -> 2*2 + 3*3*2 로 생각하여 풀이하여 문제를 해결할 수 있었다.

 

풀이 방법은 다음과 같다.

1. '(' 혹은 '[' 이 주어지면 stack에 push 한 뒤에 value값에 2 혹은 3을 곱한다.

2-1 ')' 혹은 ']' 가 주어졌을 때 stack이 비었거나 stack의 top이 '(' 혹은 '[' 이 아니면 0출력하고 프로그램 종료

2-2. 바로 앞의 문자가 '(' 혹은 '[' 인 경우 현재의 value값을 answer에 더한 후 value를 2 혹은 3으로 나눈다. 아닌 경우 value를 2혹은 3으로 나누기만 한다.

3. 마지막에 stack이 비어있지않으면 0출력 비어있으면 answer값을 출력하고 프로그램을 종료한다.

 

#include <iostream>
#include <stack>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	stack<char> sta;
	int ans=0;
	int value = 1;
	string S;

	cin >> S;

	for (int i = 0; i < S.length(); i++)
	{
		if (S[i]=='(')
		{
			sta.push(S[i]);
			value *= 2;
		}
		else if (S[i]=='[')
		{
			sta.push(S[i]);
			value *= 3;
		}
		else if (S[i]==')')
		{
			if (sta.empty() || sta.top()!='(')
			{
				cout << 0;
				return 0;
			}
			else
			{
				if (i!=0 && (S[i - 1] == '[' || S[i - 1] == '('))
				{
					ans += value;
					value /= 2;
				}
				else
				{
					value /= 2;
				}
					sta.pop();
			}
		}
		else if (S[i]==']')
		{
			if (sta.empty() || sta.top()!='[')
			{
				cout << 0;
				return 0;
			}
			else
			{
				if (i != 0 && (S[i - 1] == '[' || S[i - 1] == '('))
				{
					ans += value;
					value /= 3;
				}
				else
				{
					value /= 3;
				}
					sta.pop();
			}
		}
	}
	if (!sta.empty())
	{
		cout << 0;
	}
	else
	{
		cout << ans;
	}
	return 0;
}