현욱은 괄호왕이야!!

[Gold III] 현욱은 괄호왕이야!! - 15926

문제 링크

성능 요약

메모리: 2812 KB, 시간: 12 ms

분류

자료 구조, 스택

제출 일자

2024년 7월 12일 14:16:14

문제 설명

여는 괄호 ‘(’와 닫는 괄호 ‘)’로 구성된 문자열에서 아래의 조건을 만족하는 문자열을 올바른 괄호 문자열이라고 부른다.

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

현욱은 친구로부터 생일 선물로 굉장히 긴 괄호 문자열을 받았다(도대체 왜 이런 걸 선물하는걸까?). 하지만 현욱은 올바른 괄호 문자열이 아니면 굉장히 싫어하기 때문에, 받은 괄호 문자열에서 연속한 일부분을 잘라서 올바른 괄호 문자열을 만들려고 한다. 그리고 이왕이면 긴 문자열이 좋으니 현욱은 부분 구간을 최대한 길게 잘라내려고 한다. 현욱을 도와 주어진 괄호 문자열에서 위의 조건을 만족하는 가장 긴 부분 문자열의 길이를 계산하는 프로그램을 작성해보자.

입력

첫 줄에 문자열의 길이 n (1 ≤ n ≤ 200,000)이 주어진다.

둘째 줄에 괄호로만 구성된 길이 n짜리 문자열이 주어진다.

출력

주어진 문자열에서 길이가 가장 길면서 올바른 괄호 문자열인 부분 문자열의 길이를 출력한다. 올바른 괄호 문자열인 부분 문자열을 찾을 수 없는 경우 0을 출력한다.

---

기본적으로 Stack을 이용한 로직인 것은 쉽게 파악하였다.

그러나, Stack에 -1을 집어넣는 트릭과, 연속된 올바른 괄호 문자열을 어떻게 처리해야 할지 막막했던 문제

Stack의 Top이 유효한 문자열의 시작 인덱스를 나타내게 하는 로직을 이용해 해결

여는 괄호 ‘(‘ 는 무조건 Stack에 Push 닫는 괄호 ‘)’는 짝이 있으면 ret을 갱신(max이용), 짝이 없으면 Stack의 Top을 갱신

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

int n;
int ret;
int main(){

    cin>>n;
    stack<int> stk;
    stk.push(-1);
    for(int i=0;i<n;i++){
        char tmp;
        cin>>tmp;
        if(tmp=='('){
            stk.push(i);
        }
        if(tmp==')'){
            stk.pop();
            if(!stk.empty()){
                ret=max(ret,i-stk.top());
            }else{
                stk.push(i);  // If there's no '(' before ')', push current index to stack.
            }
        }
    }
    cout<<ret<<endl;
    return 0;
}