[ BOJ ] 20052 : 괄호 문자열 ? ( PLATINUM 4 ) / C

문제

괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다.

1. 빈 문자열은 올바른 괄호 문자열이다.
2. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이다.
3. S와 T가 올바른 괄호 문자열이라면, ST도 올바른 괄호 문자열이다.
4. 모든 올바른 괄호 문자열은 위의 3개 규칙으로만 만들 수 있다.

'('와 ')'로 이루어진 괄호 문자열 S = s1s2...sN과 M개의 쿼리가 주어진다. 쿼리는 두 정수 i, j (1 ≤ i ≤ j ≤ N)로 이루어져 있고, 쿼리가 의미하는 것은 다음과 같다.

• S의 부분 문자열 SiSi+1...Sj가 올바른 괄호 문자열이면 1, 아니면 0

모든 쿼리를 수행하고, 쿼리의 결과를 누적한 값을 구해보자.

입력

첫째 줄에 문자열 S가 주어진다. 둘째 줄에 쿼리의 개수 M이 주어진다. 셋째 줄부터 M개의 줄에 쿼리가 한 줄에 하나씩 주어진다.

출력

쿼리의 결과를 누적한 값을 출력한다.

제한

• 1 ≤ |S| ≤ 100,000
• 1 ≤ M ≤ 100,000

풀이 과정

저번에 풀었던 괄호 문자열과 쿼리 문제와 비슷하지만 살짝 다르다. 저번 문제에서는 전체 괄호 문자열이 옳은지를 검사해야 했지만, 이번에는 부분 문자열이 옳은 괄호 문자열인지 출력해야 했기 때문이다. 누적 합 세그먼트 트리를 만들고, 구간 합이 0인지와 구간을 검사할 때 구간 왼쪽 부분의 누적합을 삭제하고 계산하여 부분합의 최솟값이 음수가 되지 않을 때를 체크했다. 살짝의 생각이 필요한 문제였다.

#include <stdio.h>
#include <string.h>
#define SIZE 100005

char str[SIZE];

int arr[SIZE] = { 0, };
int tree[SIZE * 4][2] = { 0, };
int type = 0;

int min(int a, int b) {
	return (a < b ? a : b);
}

void init(int start, int end, int idx, int left) {
	if (start == end) {
		tree[idx][0] = arr[start];
		tree[idx][1] = left + arr[start];
		return;
	}

	int mid = (start + end) / 2;
	init(start, mid, idx * 2, left);
	init(mid + 1, end, idx * 2 + 1, left + tree[idx * 2][0]);
	tree[idx][0] = tree[idx * 2][0] + tree[idx * 2 + 1][0];
	tree[idx][1] = min(tree[idx * 2][1], tree[idx * 2 + 1][1]);
}

int interval_tree(int start, int end, int idx, int left, int right) {
	if (end < left || right < start) return 0;
	if (left <= start && end <= right) return tree[idx][0];

	int mid = (start + end) / 2;
	return interval_tree(start, mid, idx * 2, left, right) + interval_tree(mid + 1, end, idx * 2 + 1, left, right);
}

int interval_sums(int start, int end, int idx, int left, int right, int* error, int minus) {
	if (end < left || right < start) {
		*error = 1;
		return 0;
	}
	if (left <= start && end <= right) {
		*error = 0;
		return tree[idx][1] - minus;
	}

	int mid = (start + end) / 2;
	int e1 = 0;
	int q1 = interval_sums(start, mid, idx * 2, left, right, &e1, minus);
	int e2 = 0;
	int q2 = interval_sums(mid + 1, end, idx * 2 + 1, left, right, &e2, minus);
	if (e1 == 1 && e2 == 1) {
		*error = 1;
		return 0;
	}
	else if (e1 != 1 && e2 != 1) return min(q1, q2);
	else {
		if (e1 == 1) return q2;
		else return q1;
	}
}

int getVal(int start, int end, int idx, int what, int* er) {
	if (what < start || end < what) {
		*er = 1;
		return 0;
	}
	if (start == end) {
		*er = 0;
		return tree[idx][1];
	}

	int mid = (start + end) / 2;
	int e1 = 0;
	int q1 = getVal(start, mid, idx * 2, what, &e1);
	int e2 = 0;
	int q2 = getVal(mid + 1, end, idx * 2 + 1, what, &e2);
	if (e1 == 1 && e2 == 1) {
		*er = 1;
		return 0;
	}
	else {
		*er = 0;
		if (e1 != 1) return q1;
		else return q2;
	}
}

int main(void) {
	scanf("%s", str);

	int n = strlen(str);

	for (int i = 0; i < n; i++) {
		if (str[i] == '(') arr[i] = 1;
		else arr[i] = -1;
	}

	init(0, n - 1, 1, 0);
	int m;
	scanf("%d", &m);

	int result = 0;

	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);

		int it = interval_tree(0, n - 1, 1, a - 1, b - 1);
		int ise = 0;
		int minusVal = 0;
		if (a - 1 != 0) {
			int gve = 0;
			minusVal = getVal(0, n - 1, 1, a - 2, &gve);
		}
		int is = interval_sums(0, n - 1, 1, a - 1, b - 1, &ise, minusVal);
		if (it == 0 && is >= 0 && ise == 0) {
			result += 1;
		}
	}

	printf("%d", result);
	return 0;
}