[백준]괄호 문자열 ?(20052)

문제 링크 : [백준]괄호 문자열 ?(20052)

20052번: 괄호 문자열 ?

문제 설명

괄호문자열이 주어지고, M개의 쿼리가 주어집니다.

M개의 쿼리 중 X~Y 구간의 문자열이 옳바른 문자열인지를 판단하여 옳바른 문자열이 몇 개인지 출력하세요.

입력

S(괄호 문자열, 1 <= |S| <= 100,000)

M(쿼리의 갯수, 1 <= M <= 100,000)

X Y(쿼리 정보) 

()()()()
8
1 8
2 7
3 6
2 8
1 5
5 8
2 4
4 8

 

출력

3

 

카테고리

#세그먼트트리 #누적합

 

시간 복잡도 상한

O(Mlog|S|)

 

해결 방법

1. 옳바른 괄호 문자열의 조건은 아래와 같습니다.
   1. 여는 괄호와 닫는 괄호의 갯수가 동일합니다.
   2. 왼쪽부터 오른쪽으로 진행하면서 여는 괄호와 닫는 괄호의 수를 셀 때, 닫는 괄호가 여는 괄호보다 많으면 안됩니다.
2. 1번 조건은 여는 괄호를 1, 닫는 괄호를 -1로 치환하여 구간합을 구할 때, 그 합이 0인지를 보면 됩니다.
3. 2번 조건은 시작점부터 도착점까지 전구간에 걸쳐 구간합이 0 이상인지를 확인하면 됩니다.
4. 즉, 최소값이 0이상인지 확인하면 됩니다.
5. 구간합은 누적합으로 O(N)의 시간에 구할 수 있고, 구간의 최소값은 세그먼트 트리를 이용하여 O(log|S|)의 시간에 구할 수 있습니다.

시간복잡도

O(Mlog|S|)

코드

#include<iostream>
#include<algorithm>
#define N 100001
using namespace std;
char s[N];
int n,m,t[N*4],a[N],x,y,z;
int in(int p,int l,int r){
    if(l==r)return t[p]=a[l];
    return t[p]=min(in(p*2,l,(l+r)/2),in(p*2+1,(l+r)/2+1,r));
}
int q(int p,int l,int r,int x,int y){
    if(y<l||r<x)return 100001;
    if(x<=l&&r<=y)return t[p];
    return min(q(p*2,l,(l+r)/2,x,y),q(p*2+1,(l+r)/2+1,r,x,y));
}
int main(){
    cin>>s;
    for(;s[n];n++)a[n+1]=a[n]+(s[n]=='('?1:-1);
    in(1,1,n);
    cin>>m;
    while(m--){
        cin>>x>>y;
        z+=(a[y]==a[x-1]&&q(1,1,n,x,y)>=a[x-1]);
    }
    cout<<z;
}