취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 20052번 문제인 괄호 문자열 ?이다.
문제는 아래 링크를 확인하자.

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

'('를 +1, ')'를 -1로 생각해 prefix sum을 구한 배열 psum을 준비하자.

이 때 어떤 부분문자열 [L,R]이 올바른 괄호문자열이라면 '('로 시작해 ')'로 끝나며 '('과 ')의 개수가 같으므로 psum[R]과 psum[L-1]의 값이 같아야 하고, 어떤 순간에도 등장한 여는 괄호의 수가 닫는 괄호의 수보다 많거나 같아야하므로 min(psum[L..R])의 값이 psum[R]과 같아야 함을 알 수 있다.

위의 두 조건만을 만족하면 부분문자열 s[L..R]은 올바른 괄호문자열이기도 하므로 각 쿼리별로 위 조건들을 체크해 문제를 해결하자. 구간합 배열 및 RMQ를 구하기 위한 트릭(세그먼트트리, sparse table, Arpa's Trick 등)을 이용해 빠르게 해낼 수 있다.

아래는 제출한 소스코드이다.

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

int N, Q; string s;
int arr[100001];
int seg[262145];

int init(int L, int R, int sI) {
	if (L < R) return seg[sI] = min(init(L, (L + R) / 2, sI * 2), init((L + R) / 2 + 1, R, sI * 2 + 1));
	return seg[sI] = arr[L];
}

int qry(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return 1000000007;
	if (qL <= L && R <= qR) return seg[sI];
	return min(qry(L, (L + R) / 2, qL, qR, sI * 2), qry((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}

int ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> s; N = s.length();
	for (int i = 0; i < N; i++) arr[i + 1] = arr[i] + (s[i] == '(' ? 1 : -1);

	init(1, N, 1);

	cin >> Q;
	while (Q--) {
		int L, R; cin >> L >> R;
		if (s[L - 1] == '(' && s[R - 1] == ')' && arr[L] == arr[R] + 1 && qry(1, N, L, R, 1) >= arr[R]) ans++;
	}

	cout << ans;
}