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

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

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

 

- 문제 요약

 

첫 줄에 문자열의 길이 n(1<=n<=200,000)이 주어지고, 그 다음 줄에 길이 n의 괄호 문자열이 주어진다.

괄호 문자열에는 조건이 있는데, 아래의 조건들을 만족하면 올바른 괄호 문자열이다.

1. 어떤 문자열 x가 올바른 괄호 문자열이라면, (x)도 올바른 괄호 문자열이다.
2. 어떤 문자열 x와 y가 올바른 괄호 문자열이라면, xy도 올바른 괄호 문자열이다.

주어진 문자열에서 길이가 가장 길면서 올바른 괄호 문자열인 부분 문자열의 길이를 출력한다.

올바른 괄호 문자열인 부분 문자열을 찾을 수 없는 경우 0을 출력한다.

 

 

- 알고리즘 정리

 

우선 Tast case들을 보면서 알고리즘을 만들어보겠습니다.

 

Tast case 1

5

(())(

 

Tast case 2

14

(()))()((()))(

 

노트에 적힌 글을 보겠습니다.

 

첫 번째 입출력에서, 맨 처음 위치부터 4개를 잘라낸 (())가 가장 긴 올바른 괄호 문자열이다.

두 번째 입출력에서, 6번째 위치부터 8개를 잘라낸 ()((()))가 가장 긴 올바른 괄호 문자열이다.

 

여기서 가장 긴 부분 괄호 문자열이 되는 경우를 보면, '('와 ')'의 개수가 같은 것을 볼 수 있습니다.

이를 활용해서 스택에 문자열을 넣으며 반복문을 돌리면 될 것 같습니다.

empty를 활용하여 스택이 비어있냐, 비어있지 않느냐에 따라서 조건문으로 스택에 push, pop을 해주겠습니다.

 

 

- 코드 작성

 

우선 가장 긴 부분 괄호 문자열의 길이를 저장하는 변수 num을 선언하겠습니다.

sum의 최대 크기는 n의 최대 크기와 같으니 그냥 int형으로 선언해도 될 것 같습니다.

 

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

int n,num;
string a;
stack<int>w;

int main(){
	cin>>n>>a;
	w.push(-1);
	for(int i=0;i<n;i++){
		if(a[i]=='('){
			w.push(i);
		}
		else{
			w.pop();
			if(!w.empty()){//비어있지 않다면 
				num=max(num,i-w.top());
			}
			else{//비어있다면 
				w.push(i);
			}
		}
	}
	cout<<num;
	return 0;
}

코드 제출 결과

처음에 스택을 비워두고 시작해서 런타임 에러가 떠버렸습니다...ㅋㅋ

문제 자체는 간단하네요.