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

작성일 | In

문제 링크

  • http://icpc.me/15926

문제 출처

  • 제2회 천하제일 코딩대회 K번

사용 알고리즘

  • 스택

시간복잡도

  • O(n)

풀이

특정 문자열이 유효한 괄호 문자열인지 판별하는 방법은 ( 가 나올 경우 스택에 현재 위치를 넣고, ) 가 나온다면 스택에서 원소 하나를 제거해주면 됩니다.
스택에서 원소를 제거하려는데 underflow가 뜨거나, 문자열을 모두 탐색했는데 스택에 원소가 남아있다면 괄호 문자열이 아닙니다.
이 점을 이용하여 문제를 풀어봅시다.

스택의 맨 밑에는 (유효한 괄호 문자열이 시작되는 위치 - 1)이 있도록 유지를 합시다. 초기 상태에는 -1이 있겠죠.
( 가 나온다면 스택에 현재 위치를 넣습니다.
) 가 나와서 pop을 한 이후에는 두 가지 경우로 나뉘게 됩니다.

  1. 스택이 비어있다.
  2. 스택이 비어있지 않다.

스택이 비어있다면 유효하지 않은 괄호 문자열이므로 현재 위치를 스택에 넣습니다.
반대의 경우에는 유효한 괄호 문자열이므로 (현재위치 - stack.top())값을 정답과 비교해 적절히 갱신해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int n;
string str;
stack<int> s;

int main(){
	cin >> n >> str;
	s.push(-1);
	int ans = 0;
	for(int i=0; i<n; i++){
		if(str[i] == '(') s.push(i);
		else{
			s.pop();
			if(!s.empty()) ans = max(ans, i - s.top());
			else s.push(i);
		}
	}
	cout << ans;
}