boj2504-풀이

boj.kr/2504 괄호의 값 (문제)

풀이

---

스택을 이용하는 구현문제

1. 현재 문자가 ( 또는 [
   스택에 현재 문자 넣기(push)
   괄호의 수 + 1
2. 현재 문자가 ) 또는 ]
   1. 스택에서 ( 또는 [ 까지 pop해서 합 구하기
      • 올바른 괄호쌍의 경우 괄호의 수 - 1
      • 예외처리 : 현재 문자는 ), 스택의 맨 위 문자는 [
      • 예외처리 : 현재 문자는 ], 스택의 맨 위 문자는 (
   2. 합이 0인 경우, 스택에 2 또는 3 넣기
      • ()의 경우, 합이 0이 나온다.
   3. 합이 0이 아닌 경우, 스택에 합 * (2 또는 3)넣기
      • (())의 경우, (가장 오른쪽 괄호가 처리될 때) 합이 2가 나옴
        스택이 ((일때, )를 만나서, 스택은 (2가 된다. (3번에 의해)
        스택이 (2일때, )를 만나서, 스택은 4가 된다. (이때 합이 2)
3. 1번 ~ 2번을 입력된 모든 문자에 대해서 반복
4. 괄호의 수가 0이 아니면 오류 출력
   • 예외처리 : 스택에 괄호가 남아있다는 뜻으로 (()처럼 올바른 괄호쌍이 아님
5. 스택에 남은 수들의 합을 구하여 결과값으로 출력
   • ()()의 경우, 스택에 2,2가 남게된다.
     이 경우 합을 구해서 출력해주면 정답

구현

---

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

string s;
stack<int> st;
int brackets;

int main() {
	cin >> s;
	for (char c : s) {
		switch (c) {
		case '(':
		case '[':
			st.push(c);
			++brackets;
			break;
		case ')':
		{
			int sum = 0;
			while (true) {
				if (st.empty() || st.top() == '[') {
					cout << 0;
					return 0;
				}
				if (st.top() == '(') {
					st.pop();
					--brackets;
					st.push(sum ? sum * 2 : 2);
					break;
				}
				sum += st.top();
				st.pop();
			}
			break;
		}
		case ']':
		{
			int sum = 0;
			while (true) {
				if (st.empty() || st.top() == '(') {
					cout << 0;
					return 0;
				}
				if (st.top() == '[') {
					st.pop();
					--brackets;
					st.push(sum ? sum * 3 : 3);
					break;
				}
				sum += st.top();
				st.pop();
			}
			break;
		}
		}
	}
	if (brackets) {
		cout << 0;
		return 0;
	}
	int result = 0;
	while (!st.empty()) {
		result += st.top();
		st.pop();
	}
	cout << result;
	return 0;
}

TMI

---

전역전 휴가~ :)