백준20052 괄호 문자열 ?

작성일 | In

문제 링크

  • http://icpc.me/20052

사용 알고리즘

  • 세그먼트 트리

시간복잡도

  • $O(Q \log N)$

풀이

어떤 부분 문자열이 valid한 괄호 문자열이라는 것은

  • 여는 괄호를 1, 닫는 괄호를 -1로 치환했을 때 구간의 합이 0이고
  • 구간의 Prefix Sum의 최솟값이 0 이상인 경우를 의미합니다.

세그먼트 트리를 이용해 문제를 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int tree[1 << 18];
const int sz = 1 << 17;
void update(int x, int v){
	x |= sz; tree[x] = v; while(x >>= 1) tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
}
int query(int l, int r){
	l |= sz; r |= sz; int ret = 1e9;
	while(l <= r){
		if(l & 1) ret = min(ret, tree[l++]);
		if(~r & 1) ret = min(ret, tree[r--]);
		l >>= 1; r >>= 1;
	}
	return ret;
}

int n, q; string s;
int a[101010], sum[101010];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> s >> q; n = s.size(); s = "#" + s;
    for(int i=1; i<=n; i++){
    	a[i] = s[i] == '(' ? 1 : -1;
    	sum[i] = sum[i-1] + a[i];
    	update(i, sum[i]);
    }
    int ans = 0;
    while(q--){
    	int s, e; cin >> s >> e;
    	int mn = query(s, e) - sum[s-1];
    	if(sum[e] - sum[s-1] == 0 && mn >= 0) ans++;
    }
    cout << ans;
}