[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이 정답이다.

정답 코드

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