백준 2504번 괄호의 값

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

 

풀이 참조: [백준 BOJ / C++] 2504번: 괄호의 값

 

아이디어:

1. 스택과 이전 글자 사용

2. 최종 결과 ans(초기값 0)와 중간 계산값 tmp (초기값 1) 사용

3. 분배 법칙 활용

X(A+B) = AX + BX

4. 들어오는 ( 에 대해 미리 2를 곱하고

5. 들어오는 ) 에 대해

5-1. 스택이 비었거나 이전 문자가 ( 가 아니라면

0 출력하며 종료

5-2. 이전 문자가 ( 이면

ans에 tmp를 더하고 tmp는 2로 나누기

5-3. 이전 문자가 ( 이 아니면

tmp를 2로 나누기

6. [ 와 ] 도 똑같이 적용

 

) 와 ] 에서만 계산하는게 아니라

( 와 [ 에서도 곱셈을 해주면서 ) 와 ]에서 tmp를 더하고 나눗셈으로 tmp를 풀어주는 과정이 중요

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int tmp = 1, ans = 0;
	char pre = ' ';
	string str;
	stack<char> S;

	cin >> str;

	for (auto i : str) {
		if (i == '(') {
			tmp *= 2;
			S.push(i);
		}
		else if (i == '[') {
			tmp *= 3;
			S.push(i);
		}
		else if (i == ')') {
			if (S.empty() || S.top() != '(') {
				ans = 0;
				break;
			}
			else if (pre == '(') {
				ans += tmp;
				tmp /= 2;
				S.pop();
			}
			else if (pre != '(') {
				tmp /= 2;
				S.pop();
			}
		}
		else if (i == ']') {
			if (S.empty() || S.top() != '[') {
				ans = 0;
				break;
			}
			else if (pre == '[') {
				ans += tmp;
				tmp /= 3;
				S.pop();
			}
			else if (pre != '[') {
				tmp /= 3;
				S.pop();
			}
		}

		pre = i;
	}
	
	if (!S.empty()) {
		cout << 0;
		return 0;
	}

	cout << ans;

	return 0;

}