[ BOJ ] 17407 : 괄호 문자열과 쿼리 ( PLATINUM 3 ) / C

문제

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

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

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

• S의 i번째 문자가 '('면 ')'로, ')'면 '('로 변경한다.

쿼리의 수행은 누적되며, i번째 쿼리는 i-1번째 쿼리가 수행된 결과에 수행되어야 한다. 각 쿼리를 수행한 결과가 올바른 괄호 문자열이었던 횟수를 모두 세어보자.

입력

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

출력

첫째 줄에 쿼리를 수행한 결과가 올바른 괄호 문자열이었던 횟수를 출력한다.

풀이 과정

와 ㅋㅋ 이거 그냥 ( 을 1로 바꾸고 ) 을 -1로 바꾼 다음 0이 되면 옳은 문자열이네! 구간 합 세그 트리 구해서 만들어야지! 라고 생각했다가 틀렸던 문제였다. 알고보니 ))(( 같은 ) 가 먼저 나오는 경우를 고려해야 했었고, 이를 구하기 위해 누적합 최소 레이지 세그 트리를 구해서, 누적합을 구하다가 만약 음수가 나오는 경우 ( ex. (()))) , ))(( ) 올바르지 않은 문자열로 간주한다.

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

char str[SIZE];

int arr[SIZE] = {0,};
int tree[SIZE * 4] = { 0, };
int sums[SIZE * 4] = { 0, };
int lazy[SIZE * 4] = { 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] = arr[start];
		sums[idx] = left + arr[start];
		lazy[idx] = 0;
		return;
	}

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

void update_tree(int start, int end, int idx, int what) {
	if (what < start || end < what) return;
	if (start == end) {
		tree[idx] = (tree[idx] == 1) ? -1 : 1;
		type = tree[idx];
		return;
	}

	int mid = (start + end) / 2;
	update_tree(start, mid, idx * 2, what);
	update_tree(mid + 1, end, idx * 2 + 1, what);
	tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

void update_lazy(int start, int end, int idx) {
	if (lazy[idx] != 0) {
		sums[idx] += (2 * lazy[idx]);
		if (start != end) {
			lazy[idx * 2] += lazy[idx];
			lazy[idx * 2 + 1] += lazy[idx];
		}
		lazy[idx] = 0;
	}
}
void update_sums(int start, int end, int idx, int left, int right) {
	update_lazy(start, end, idx);
	if (end < left || right < start) return;
	if (left <= start && end <= right) {
		sums[idx] += (2 * type);
		if (start != end) {
			lazy[idx * 2] += type;
			lazy[idx * 2 + 1] += type;
		}
		return;
	}

	int mid = (start + end) / 2;
	update_sums(start, mid, idx * 2, left, right);
	update_sums(mid + 1, end, idx * 2 + 1, left, right);
	sums[idx] = min(sums[idx * 2], sums[idx * 2 + 1]);
}

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 num;
		scanf("%d", &num);

		update_tree(0, n - 1, 1, num - 1);
		update_sums(0, n - 1, 1, num - 1, n - 1);
		if (tree[1] == 0 && sums[1] >= 0) {
			result += 1;
		}
	}

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