백준 20052번 괄호 문자열?

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

20052번: 괄호 문자열 ?

풀이

유니온 파인드를 이용한 풀이와 세그먼트 트리를 이용한 풀이가 있습니다.

유니온 파인드 풀이는 제가 구상했고, 세그먼트 트리 풀이는 다른 분의 도움을 받았습니다.

 

풀이 1(유니온 파인드 이용)

이 풀이의 핵심은 유니온 파인드를 이용해 이어져 있는 괄호쌍을 하나로 묶어 관리하는 것입니다. 입력받은 괄호 문자열을 탐색하며 이어져 있는 괄호쌍을 묶는 작업을 마치면 아래 그림처럼 괄호 문자열이 여러 개의 그룹으로 나누어집니다. 같은 색의 괄호끼리 같은 그룹입니다.

이렇게 그룹을 나누면 임의의 구간이

• 시작점이 ( 인가
• 끝점이 ) 인가
• 시작점과 끝점이 같은 그룹에 속해 있는가

세 조건을 만족하는지 검사하여 구간이 올바른 괄호 문자열인지 검사할 수 있습니다. 유니온파인드 연산을 상수 시간이라고 생각하면 시간복잡도는 $O(N + M)$입니다. ($N$은 입력받은 문자열의 길이이며, $M$은 쿼리의 개수입니다)

코드

#include <bits/stdc++.h>
#define S (100000 + 5)
using namespace std;
struct ele {
    char ch;
    int idx;
};
stack<ele> stk;
string got;
int save[S], uf[S];
bool chk[S];
int find(int a) {
    if (!uf[a])
        return a;
    return uf[a] = find(uf[a]);
}
void merge(int a, int b) {
    int a_r = find(a);
    int b_r = find(b);
    if (a_r != b_r)
        uf[a_r] = b_r;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int m, s, e;
    cin >> got;
    int l = got.length();
    for (int i = 0; i < l; i++) {
        if (stk.empty() or stk.top().ch == ')' or stk.top().ch == got[i])
            stk.push({ got[i], i + 1 });
        else {
            save[i + 1] = stk.top().idx;
            save[stk.top().idx] = i + 1;
            merge(stk.top().idx, i + 1);
            stk.pop();
        }
    }
    for (int i = 1; i < l - 2; i++) {
        if (got[i - 1] == '(' and got[save[i]] == '(' and save[save[i] + 1])
            merge(i, save[i] + 1);
    }
    cin >> m;
    int ans = 0;
    while (m--) {
        cin >> s >> e;
        ans += got[s - 1] == '(' and got[e - 1] == ')' and find(s) == find(e);
    }
    cout << ans;
    return 0;
}

29~38번째 줄에서 문자열을 한 번 쭉 탐색하며 각 괄호의 쌍을 찾아 하나의 그룹으로 묶어줍니다. 39~42번째 줄에서는 다시 문자열을 탐색하며 묶은 괄호 쌍들 중 인접한 것들을 찾아 하나의 그룹으로 묶습니다. 이후 구간을 m번 입력받아 세 가지를 검사하여 올바른 괄호 문자열인지 판별합니다.

 

풀이 2(세그먼트 트리 이용)

아래 두 조건을 모두 만족하는 구간은 올바른 괄호 문자열입니다.

• 전체 구간의 여는 괄호의 수와 닫는 괄호의 수가 같은가?
• 구간에서 닫는 괄호의 수가 여는 괄호의 수보다 더 많은 순간이 있는가?

두 번째 조건을 만족하지 않는 문자열은 

 

(()))(

 

이 있습니다. 5번째 괄호를 볼 때 닫는 괄호 3개, 여는 괄호 2개로 괄호 문자열을 만들 수 없습니다. 위 두 조건은 여는 괄호 ( 를 1로, 닫는 괄호 ) 를 -1로 생각하고 문자열에 대한 누적합 배열을 구하여 검사할 수 있습니다.

이 문자열을 배열과 누적합 배열로 만들면 아래처럼 됩니다.

 

[1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, -1] // 배열
[1, 2, 3, 2, 3, 2, 1, 2, 3, 2, 1, 0, 1, -1] // 누적합 배열

 

이 배열을 활용한다면 구간 [s, e]를 판별할 때 위에서 제시한 2개의 조건을 아래와 같이 고쳐 쓸 수 있습니다.

• 정수 배열의 구간 [s, e]의 합이 0인가?
• 누적합 배열의 구간 [s, e]의 최솟값이 누적합 배열의 s-1번째 값보다 크거나 같은가?

첫 번째 조건은 누적합 배열만으로 검사할 수 있으며, 누적합 배열의 구간 최솟값을 구하는 세그먼트 트리를 사용하면 두 번째 조건도 시간 안에 검사할 수 있습니다. 문자열의 길이를 $N$, 쿼리의 수를 $M$이라고 하면 최솟값을 찾는 $O(logN)$ 작업을 $M$번 반복하므로 총 시간복잡도는 $O(MlogN)$입니다.

코드

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0), cin.tie(nullptr)
#define all(v) v.begin(), v.end()
using namespace std;
void init(int now, int l, int r, vector<int>& tree, vector<int>& arr) {
    if (l == r) {
        tree[now] = arr[l];
        return;
    }
    int mid = (l + r) / 2;
    init(now * 2, l, mid, tree, arr);
    init(now * 2 + 1, mid + 1, r, tree, arr);
    tree[now] = min(tree[now * 2], tree[now * 2 + 1]);
}
int getmin(int now, int nowl, int nowr, int l, int r, vector<int>& tree) {
    if (nowr < l or r < nowl)
        return (int)1e9;
    if (l <= nowl and nowr <= r)
        return tree[now];
    int mid = (nowl + nowr) / 2;
    return min(getmin(now * 2, nowl, mid, l, r, tree), getmin(now * 2 + 1, mid + 1, nowr, l, r, tree));
}
string s;
int main() {
    fast;
    int m, a, b;
    cin >> s >> m;
    vector<int> presum(1), tree(s.length() * 4);
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '(')
            presum.push_back(presum.back() + 1);
        else
            presum.push_back(presum.back() - 1);
    }
    init(1, 1, s.length(), tree, presum);
    int ans = 0;
    while (m--) {
        cin >> a >> b;
        if (presum[b] - presum[a - 1] == 0 and getmin(1, 1, s.length(), a, b, tree) >= presum[a - 1])
            ans++;
    }
    cout << ans;
    return 0;
}

 

사족

거의 최단 경로 문제의 풀이가 재채점 이후 시간 초과를 받아서 이 문제가 저 스스로 온전히 풀어낸 첫 플레 문제가 되었어요 

 

세그먼트 트리로 많이 푸시는 것 같은데 나름 다른 풀이를 생각해낸 것 같아서 기분이 좋아요