[P3] 백준 17407번 괄호 문자열과 쿼리 C++ 세그먼트 트리

리뷰

 

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

토글 방식을 사용하는 아주 기가막힌 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• Node : 현재 괄호 상태를 정의할 구조체
• tree : 세그먼트 트리 정보를 저장할 Node타입 배열
• lst : 각 리프 노드 상태를 저장할 Node타입 배열
• s : 초기 괄호 상태를 저장할 문자열
• n : 노드의 개수를 저장할 변수
• m : 쿼리의 개수를 저장할 변수

 

함수

1. build

void build(int node, int s, int e) {
	if (s == e) tree[node] = lst[s];
	else {
		int mid = (s + e) / 2;
		build(node * 2, s, mid);
		build(node * 2 + 1, mid + 1, e);

		Node L = tree[node * 2], R = tree[node * 2 + 1];		
		int del = min(L.o, R.c);
		tree[node] = { L.o + R.o - del, L.c + R.c - del };
	}
}

 

세그먼트 트리 초기화를 하기 위한 함수

 

2. update

void update(int node, int s, int e, int idx, Node val) {
	if (s == e) tree[node] = val;
	else {
		int mid = (s + e) / 2;
		if (idx <= mid) update(node * 2, s, mid, idx, val);
		else update(node * 2 + 1, mid + 1, e, idx, val);

		Node L = tree[node * 2], R = tree[node * 2 + 1];
		int del = min(L.o, R.c);
		tree[node] = { L.o + R.o - del, L.c + R.c - del };
	}
}

 

세그먼트 트리 업데이트를 하기 위한 함수

 

 

문제풀이

1. s값을 입력 받고, n을 s의 크기로 초기화한다.
2. s를 순회하며 현재 문자가 '('면 해당 노드를 {1, 0}, ')'면 {0, 1}로 lst배열을 초기화한다.
3. build함수를 호출하여 초기 세그먼트 트리 정보를 초기화한다.
4. m값을 입력 받고, 변수 cnt를 0으로 초기화한다.
5. m번의 while문을 수행하고, 변수 i에 변경하고자 하는 노드 번호를 입력받는다.
6. 먼저 해당 노드가 {1, 0}이면 {0, 1}로, {0, 1}이면 {1, 0}으로 변경해준다.
7. update함수를 통해 i번쨰 노드를 lst[i]값으로 변경 후 세그먼트 트리 정보를 업데이트한다.
8. 세그먼트 트리의 루트 노드가 {0, 0}이면 cnt를 증가시킨다.
9. 모든 쿼리를 수행한 후에 cnt에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 알고리즘 분류에 느리게 갱신되는 세그먼트 트리가 있지만 구간 업데이트가 꼭 필요한가? 생각이 들었다.
2. 토글을 사용해 리프 노드부터 루트 노드까지 갱신하고, 루트 노드 상태를 O(1)로 확인할 수 있었다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 1e5 + 1;
struct Node {
	int o, c;
};
Node tree[N * 4];
Node lst[N];
string s;
int n, m;

void build(int node, int s, int e) {
	if (s == e) tree[node] = lst[s];
	else {
		int mid = (s + e) / 2;
		build(node * 2, s, mid);
		build(node * 2 + 1, mid + 1, e);

		Node L = tree[node * 2], R = tree[node * 2 + 1];		
		int del = min(L.o, R.c);
		tree[node] = { L.o + R.o - del, L.c + R.c - del };
	}
}

void update(int node, int s, int e, int idx, Node val) {
	if (s == e) tree[node] = val;
	else {
		int mid = (s + e) / 2;
		if (idx <= mid) update(node * 2, s, mid, idx, val);
		else update(node * 2 + 1, mid + 1, e, idx, val);

		Node L = tree[node * 2], R = tree[node * 2 + 1];
		int del = min(L.o, R.c);
		tree[node] = { L.o + R.o - del, L.c + R.c - del };
	}
}

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

	cin >> s;
	n = s.size();
	for (int i = 1; i <= n; ++i) {
		char c = s[i - 1];
		if (c == '(') lst[i] = { 1, 0 };
		else lst[i] = { 0, 1 };
	}
	build(1, 1, n);

	cin >> m;
	int cnt = 0;
	while (m--) {
		int i; cin >> i;

		if (lst[i].o) lst[i] = { 0, 1 };
		else lst[i] = { 1, 0 };

		update(1, 1, n, i, lst[i]);
		if (!tree[1].c && !tree[1].o) ++cnt;
	}
	cout << cnt;
}