[BOJ] 2504번: 괄호의 값

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/2504

2504번: 괄호의 값

 

실버 문제인데도 꽤나 시간을 많이 쓴 문제다

 

접근 방식은 다음과 같다.

 

1. 괄호가 바로 완성될 경우 즉, () 또는 [] 인 경우에는 그 값인 2와 3을 반환받아 스택에 넣어줬다.

2. (X)나 [X]와 같이 괄호 안에 X를 담고 있는 경우, 그 X는 1번에 의해 스택에 숫자로 쌓여 있을 것이다.

   따라서 X값을 차례로 계산하여 문제의 규칙에 맞게 2나 3을 곱하여 다시 스택에 넣어줬다.

 

예시로 (()[[]])의 괄호 값을 계산해보자.

2번째 괄호 (와 3번째 괄호 )는 1번에 해당한다. 따라서 해당 값 2를 스택에 넣어준다.

그 과정은 아래 그림과 같다.

 

 

그 다음 등장하는 [는 바로 완성되는 괄호가 아니므로 스택에 쌓인다.

하지만 그 다음 [는 연달아 ]가 와서 완성되므로 해당하는 값인 3을 스택에 push해준다.

 

 

이제 등장하는 ]는 앞에 존재할 [에 대한 괄호이 끝을 의미한다.

하지만 지금 스택의 top에는 3이라는 숫자가 존재한다.

즉, [X]의 형태를 나타내는 것이다.

 

따라서 [이 등장할 때까지 그 사이 숫자들을 더해줌으로써 X값을 계산해준 뒤,

[를 만나면 X값에 3을 곱한 값을 다시 스택에 push해준다.

 

 

그 다음 등장하는 )는 스택 어딘가에 쌓여 있을 (에 대한 짝이다.

이 경우에 ( 위에 2와 9가 쌓여 있으므로 그 값들을 각각 pop해준 뒤 더해서 X값을 계산해줘야 한다.

따라서 (X)에 해당하는 X는 11일 것이고 규칙에 의해 (X)값은 2*9 = 18일 것이다.

이는 위의 과정과 똑같으므로 그림을 생략한다.

 

코드에서 그 밖에 올바른 괄호열인지 체크하는 부분때문에 코드가 상당히 지저분해졌다.

다음에 풀어볼 때는 더 좋은 풀이를 공부해서 풀어봐야겠다.

 

/*
20200508
baekjoon 2504번 - 괄호의 값
solved
*/
#include <iostream>
#include <vector>
#include <stack>
#include <string>
using namespace std;

int main() {
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	string input;
	cin >> input;

	int res = 0, tmp = 0; stack<string>st; bool found = true; int op1 = 0, op2 = 0, cl1 = 0, cl2 = 0;
	for (int i = 0; i < input.size(); ++i) {
		if (input[i] == '(') op1++;
		else if (input[i] == '[') op2++;
		else if (input[i] == ')')cl1++;
		else cl2++;
	}
	
	if (op1 != cl1 || op2 != cl2) {
		cout << 0;
		return 0;
	}

	for (int i = 0; i < input.size(); ++i) {
		if (input[i] == '(' || input[i] == '[') {
			st.push(to_string(input[i]));
		}
		else if (input[i] == ')') {
			if (st.empty()) {
				found = false;
				break;
			}
			if (input[i - 1] == '(') {
				st.pop();
				st.push("2");
			}
			else {
				while (st.top() != to_string('(')) {
					if (st.top() == to_string('[')) {
						found = false;
						break;
					}
					tmp += (atoi(st.top().c_str()));
					st.pop();
				}
				
				st.pop();
				st.push(to_string(tmp * 2));
				tmp = 0;
			}
		}
		else {
			if (st.empty()) {
				found = false;
				break;
			}
			if (input[i - 1] == '[') {
				st.pop();
				st.push("3");
			}
			else {
				while (st.top() != to_string('[')) {
					if (st.top() == to_string('(')) {
						found = false;
						break;
					}
					tmp += (atoi(st.top().c_str()));
					st.pop();
				}
				
				st.pop();
				st.push(to_string(tmp * 3));
				tmp = 0;
			}
		}
	}

	if (found) {
		while (!st.empty()) {
			res += atoi(st.top().c_str());
			st.pop();
		}

		cout << res;
	}
	else {
		cout << 0;
	}
}