[C++] BOJ(백준) 15926 현욱은 괄호왕이야!!

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

15926번: 현욱은 괄호왕이야!!

 

스택 문제다.

 

올바른 괄호 부분 문자열 중 길이가 가장 긴 것을 찾는 것이다.

처음에는 일반 괄호 짝 맞추기처럼 여는 괄호는 스택에 넣고 닫는 괄호를 만나면 스택에서 여는 괄호를 빼는 방법을 택했다.

이 때, 스택에 넣고 뺄 때마다 카운트를 했다.

닫힌 괄호를 만났을 때 스택이 비어 있으면 해당 사이즈 만큼 카운트를 줄였다.

((()  와 같이 열린 괄호가 많은 경우 반례가 생겼다.

 

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

위 문제를 풀었을 때 썼던 방법을 활용하기로 했다.

여는 괄호를 0으로 하고 닫힌 괄호를 만났을 때 스택에 0이 있다면 올바른 괄호 문자열 길이를 스택에 넣어주는 것이다.

즉, 0이 아닌 숫자가 스택에 들어갈 수 있고, 닫힌 괄호를 만났을 때 0이 아닌 숫자가 존재한다면

0을 만날 때까지 pop을 하면서 숫자를 더하고 0을 만나면 0 제거 후 합에 2를 더해 다시 스택에 넣는다.

())))()()())의 경우 2222가 스택에 남아 답이 8이 된다.

이 반례를 해결하고자 닫힌 괄호를 만났을 때 스택에 0이 없다면 -1을 스택에 넣어 괄호 문자열이 끊어짐을 나타냈다.

 

#include <iostream>
#include <stack>
using namespace std;

int n, res;

string s;

int main() {
	cin >> n >>s;
	stack<int> st;

	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '(') {
			st.push(0);
		}
		else {
			if (st.size() && st.top() == 0) {
				st.pop();
				st.push(2);
			}
			else if (st.size() && st.top() > 0) {
				int tmp = 0;
				while (!st.empty() && st.top() > 0) {
					tmp += st.top();
					st.pop();
				}
				if (st.size() && st.top() == 0) {
					st.pop();
					st.push(tmp + 2);
				}
				else {
					st.push(tmp);
					st.push(-1);
				}
			}
			else st.push(-1);
		}
	}

	while (!st.empty()) {
		int tmp = 0;
		while (st.size() && st.top() > 0) {
			tmp += st.top();
			st.pop();
		}
		if (st.size()) st.pop();
		res = max(res, tmp);
	}

	cout << res;

}