boj 15926 현욱은 괄호왕이야!!

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

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

주어진 입력에서 올바른 괄호쌍의 부분 문자열이 가장 긴 길이를 구하는 문제입니다.

올바른 괄호쌍을 구하기 위해서는 stack을 이용합니다.

 

기본 스택문제와 동일하게 `(`가 나오면 stack에 push, `)`가 나오면 stack에서 pop 연산을 수행합니다.

이 문제는 주어진 문자열의 인덱스를 이용합니다.

`(`가 나오면 그 인덱스를 stack에 push합니다.

`)`가 나오면 s.top의 인덱스와 현재 인덱스에 true 값을 넣습니다.

 

최종으로는 chk[i] = true인 부분의 max 길이를 구해주시면 되겠습니다.

 

 

#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
#define MAX 200001
using namespace std;
 
string str;
bool chk[MAX];
int N;
 
void func() {
    stack<int> s;
    for (int i = 0; i < N; i++) {
        if (str[i] == '(') {
            s.push(i);
        }
        else {
            if (s.empty()) continue;
 
            chk[i] = chk[s.top()] = true;
            s.pop();
        }
    }
 
    int ret = 0;
    int conn = chk[0];
    for (int i = 1; i < N; i++) {
        if (chk[i]) conn++;
        else conn = 0;
 
        ret = max(ret, conn);
    }
 
    cout << ret << '\n';
}
 
void input() {
    cin >> N >> str;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}