[백준] 2504. 괄호의 값

2504. 괄호의 값

문제를 처음 보자마자 스택을 써야겠다는 생각이 들었다. 하지만 곱셈과 덧셈을 하려니 순서가 막막했다. 아래 과정 중 3,4 번 과정을 생각해내는게 매우 힘들었던 문제이다.

(()[[]])([])를 예시로 들면 2X(2+3X3) + 2X3 의 값 28이 나온다. 여기서 분배법칙으로 풀어야 알고리즘을 더 쉽게 접근할 수 있다. (2X2 + 2X3X3 + 2X3)

알고리즘 과정

1. 반복문을 통해 각각의 문자를 읽는다.

2. 중괄호, 대괄호 중 시작하는 괄호가 나오면 스택에 저장하고, tmp라는 변수에 2 또는 3의 값을 곱해서 누적한다.

• ')'가 나오면 스택이 비어있는지 확인하고, 스택의 탑이 '('인지 확인한다.(올바르지 않은 괄호열 확인)
• 현재 문자의 직전 문자가 '('이면 sum변수에 tmp 값을 누적 시킨다.
• tmp 값을 2로 나눈다.

4. 3번 과정을 ']'로 반복한다.

5. 3, 4 과정을 반복

6. 스택이 비어 있지 않거나 올바르지 않은 괄호열이면 0 반환, 아니면 sum 반환한다.

#include <iostream>
#include <stack>
using namespace std;
int main() {
	string str;
	cin >> str;
	int sum = 0, tmp = 1;
	bool error = false;
	stack<char> st;
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '(') {
			tmp *= 2;
			st.push(str[i]);
		}
		else if (str[i] == ')') {
			if (st.empty()) {
				error = true;
				break;
			}
			if (st.top() == '(') {
				st.pop();
				if (str[i - 1] == '(')
					sum += tmp;
				tmp /= 2;
			}
			else {
				error = true;
				break;
			}
		}

		else if (str[i] == '[') {
			tmp *= 3;
			st.push(str[i]);
		}
		else if (str[i] == ']') {
			if (st.empty()) {
				error = true;
				break;
			}
			if (st.top() == '[') {
				st.pop();
				if (str[i - 1] == '[')
					sum += tmp;
				tmp /= 3;
			}
			else {
				error = true;
				break;
			}
		}
	}
	if (error || !st.empty()) {
		cout << 0;
		return 0;
	}
	cout << sum;
}