[BOJ] 백준 20052. 괄호 문자열 ? (Platinum IV)

괄호 문자열 시리즈 문제 중 하나이다.

문제는 아래와 같다.

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

20052번: 괄호 문자열 ?

사실 괄호 문자열 문제가 시리즈로 있다는 것을 이 문제로 처음 알았다.

예전에 풀어본 9935번 문자열폭발 문제랑 비슷한 줄 알았는데, 생각해보니 그 문제는 괄호가 아니라 문자열 관련 문제였다. 괄호라고 해서 스택, 카탈란수가 생각나서 비슷하게 생각했나보다.

나중에 이 문제들도 풀어봐야겠다.

---

의식의 흐름 및 해설

처음에는 스택이나 카탈란 수를 떠올렸다.

그러나 쿼리가 주어지는 특성 상 스택은 바로 생각에서 제외시킬 수 있었고, 카탈란 수에서 괄호를 1, -1로 표현해보는 방법을 생각해볼 수 있었다.

 

사실 풀이는 카탈란수랑 아무런 관련이 없으며, '('를 1, ')'를 -1로 누적합을 이용하여 풀면 된다.

우선 쿼리에서 주어지는 구간에서 누적합이 음수가 나오는 구간이 있으면 닫는괄호 개수가 여는괄호 개수보다 더 많은 경우이므로 불가능하다.

또한, 여는 괄호 개수랑 닫는 괄호 개수는 동일해야 한다.

 

이는 주어지는 쿼리가 [s, e], 누적합 배열이 p[MAX]라고 할 때,

p[e]==p[s-1]로 조건문을 걸어 해결할 수 있으며,

누적합 배열에서 [s, e] 중간에 하나라도 음수가 나오는 구간이 있는지 파악하기 위해선, 최솟값 세그먼트 트리(Range Minimum Query Segtree, 이하 RMQ segtree)로 파악해주면 된다.

RMQ는 누적합으로 처리할 수 없고, 세그먼트트리가 최선이다. 따라서 RMQ 세그트리 query(1,1,N,s,e)>=a[s-1]로 조건문을 걸어 해결할 수 있다. [s, e]중 최솟값이 a[s-1]까지의 누적합보다 작다면, [s, e] 중간에 하나라도 음수가 나오는 구간이 존재한다는 것이기 때문이다.

 

시간복잡도는 O(MlgN)으로, 누적합을 O(N)으로 미리 구해두고 쿼리 M번마다 O(lgN) 시간복잡도를 소요하기 때문이다.

---

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
const int MAX = 100011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
string s;
int N, M, a[MAX], tree[1 << 18], ans;
int init(int node, int s, int e) {
	if (s == e)
		return tree[node] = a[s];
	int mid = (s + e) / 2;
	return tree[node] = min(init(node * 2, s, mid),
		init(node * 2 + 1, mid + 1, e));
}
int query(int node, int s, int e, int left, int right) {
	if (e < left || right < s)
		return INF;
	if (left <= s && e <= right)
		return tree[node];
	int mid = (s + e) / 2;
	return min(query(node * 2, s, mid, left, right),
		query(node * 2 + 1, mid + 1, e, left, right));
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> s >> M;
	int N = s.length();
	for (int i = 1; i <= N; i++) {
		if (s[i - 1] == '(') {
			a[i] = a[i - 1] + 1;
		}
		else {
			a[i] = a[i - 1] - 1;
		}
	}
	init(1, 1, N);
	while (M--) {
		int lo, hi;
		cin >> lo >> hi;
		if (!(a[hi]-a[lo-1]) && query(1,1,N,lo,hi)>=a[lo-1])
			ans++;
	}
	cout << ans << "\n";
}

---

누적합과 세그먼트트리를 융합하는 재밌는 문제였다.

괄호 문자열은 그 성질 덕분인지 진짜 관찰하는 방법이 다양한 듯.