[BOJ] 백준 15926 현욱은 괄호왕이야!!

문제 링크

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

우선 스택을 이용해 $O(N)$의 시간복잡도로 올바른 괄호문자열의 여는 괄호, 닫는 괄호의 위치를 저장할 수 있다.

문자열 $s$와 배열 $d$에 대해

$d[i]$가 1인 경우 $s[i]$가 올바른 괄호문자열에 포함되는 괄호이고, 0인 경우 아니라고 하자.

$s[i] =$ '(' 이면 스택에 위치 i를 넣고, $s[j]$에서 $s[i]$와 쌍이 되는 닫는 괄호가 나오면 $s[i]$와 $s[j]$는 올바른 괄호 문자열에 포함되는 괄호이므로 $d[i] = d[j] = 1$이다.

스택으로 올바른 괄호문자열의 위치들을 저장했으니 배열 $d$에서 1이 최대로 연속되는 값이 답이다.

예를 들어, (())()(()의 경우 

idx	0	1	2	3	4	5	6	7	8
s	(	(	)	)	(	)	(	(	)
d	1	1	1	1	1	1	0	1	1

이며, 이때 6이 정답이다.

정답 코드

	#include <iostream>
	#include <stack>
	#include <string>
	using namespace std;
	int n, d[200001], ans;
	string s;
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	cin >> s;
	stack<int> st;
	for (int i = 0; s[i]; i++) {
	if (s[i] == '(')
	st.push(i);
	else {
	if (!st.empty()) {
	d[i] = d[st.top()] = 1;
	st.pop();
	}
	}
	}
	int val = 0;
	for (int i = 0; s[i]; i++){
	if (d[i]) {
	val++;
	ans = ans > val ? ans : val;
	}
	else {
	val = 0;
	}
	}
	cout << ans;
	}

view raw 15926.cpp hosted with ❤ by GitHub

질문, 피드백 환영합니다.