[백준(BOJ) 2504번] 괄호의 값 (C++)

문제 링크

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

 

문제 정보

입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다. 

 

풀이

 스택을 이용해서 풀이할 수 있다. 굉장히 많은 고민을 해봐도 해결하기 힘들었다. 여는 괄호 중 소괄호가 나오면 2를 num에 곱하고 스택에 push 하고, 대괄호는 3을 num에 곱하고 스택에 push 한다. 그리고 닫는 괄호 중 소괄호가 나왔을 때 괄호 쌍이 올바르다면 곱해준 num 값을 sum에 더한다. 그러면 소괄호 쌍 1개를 계산한 것이므로 스택에서 pop해서 제거해준 후 소괄호 쌍이 제거되었으므로 num을 2로 다시 나눠준다. 대괄호도 똑같이 생각하면 된다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	string str;
	cin >> str;
	
	int sum = 0; // 누적해서 더해지는 값
	int num = 1; // 곱해질 값
	
	stack<char> S;
	
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == '(') {
			num *= 2; // 소괄호 곱하기 2
			S.push(str[i]);
		} else if (str[i] == '[') {
			num *= 3; // 대괄호 곱하기 3
			S.push(str[i]);
		} else if (str[i] == ')') {
			if (S.empty() || S.top() != '(') { // 올바르지 않은 괄호 쌍
				sum = 0;
				break;
			}
			if (str[i - 1] == '(') {
				sum += num; // 앞에가 여는 괄호였다면 sum에 값을 더한다.
			}
			S.pop();
			num /= 2; // 소괄호 쌍이 사라져서 2로 나눈다.
		} else { // str[i] == ']'
			if (S.empty() || S.top() != '[') { // 올바르지 않은 괄호 쌍
				sum = 0;
				break;
			}
			if (str[i - 1] == '[') {
				sum += num; // 앞에가 여는 괄호였다면 sum에 값을 더한다.
			}
			S.pop();
			num /= 3; // 대괄호 쌍이 사라져서 3으로 나눈다.
		}
	}
	
	if (S.empty()) {
		cout << sum;
	} else { // 올바르지 않은 괄호 쌍
		cout << '0';
	}
	
	return 0;
}