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

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

2504번: 괄호의 값

---

 문제 풀이

괄호를 다루는 스택 문제이다!

이 문제의 가장 중요한 포인트는 2가지이다.

 1. 분배 법칙

 2. 계산된 값을 언제 정답에 더할지

첫 번째는 쉽다. 예제를 예로 들면 (2 + 3 * 3) * 2 가 2 *2 + 3 * 3 * 2로 계산될 수 있다는 점이다.

두 번째는 생각이 필요하다.

단순하게 닫힌 괄호가 올 때마다 정답에 더한다면 우리가 원하는 값과 다른 값을 계산한다.

닫힌 괄호가 올 때 이전의 문자가 열린 괄호라면 더 이상의 곱셈 연산이 없다는 것을 의미한다.

따라서 닫힌 괄호와 이전의 문자가 한 쌍일 때 정답에 값을 더해주면 된다.

마지막으로, 문자열의 길이만큼 반복을 했는데 스택이 비어있지 않은 것은 정상적이지 않다는 것을 의미하므로 바로 0을 리턴해주면 된다.

 느낀 점

기본적인 자료구조 문제로 쉽게 생각했지만 생각보다 애를 먹었던 문제이다. 2번 포인트를 어떻게 잡는지가 가장 중요한 문제인 것 같다!

 코드

#include <iostream>
#include <stack>
#include <string>

using namespace std;

string str;
stack<char> s;
int tmp = 1, ans = 0;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> str;
	for (int i = 0; i < str.length();i++) {
		if (s.empty() || str[i] == '(' || str[i] == '[') {
			if (str[i] == '(') tmp *= 2;
			else if (str[i] == '[') tmp *= 3;
			s.push(str[i]);
		}
		else {
			if (s.top() == '(' && str[i] == ')') {
				if (str[i - 1] == '(') ans += tmp;
				s.pop();
				tmp /= 2;
			}
			else if (s.top() == '[' && str[i] == ']') {
				if (str[i - 1] == '[')ans += tmp;
				s.pop();
				tmp /= 3;
			}
		}
	}

	if (!s.empty()) ans = 0;
	cout << ans;
}