[백준] BOJ 22343 : 괄호의 값 비교

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

22343번: 괄호의 값 비교

문제를 해석해보면 아래와 같습니다.

 

1. 함수 F가 있는데, F[()] = 1입니다.

2. F[(<괄호>)] = F[<괄호>] * 2이고, F[<괄호><괄호>] = F[<괄호>] +F[<괄호>] 이런식으로 동등한 위치에서의 괄호들의 F 값들은 더하고, 씌워져 있는 만큼 2를 곱해줍니다.

3. 괄호들이 제대로 씌워진 문자열 a,b가 주어질 때, f[a]와 f[b] 값을 비교한 결과를 출력해야 합니다.

 

일단 저는 문제를 보고, 그냥 Stack으로 구현하면 되는게 아닌가 싶었습니다. Stack으로 문자열을 살펴보면서 전에 (가 나오다가 )이 나오면 값을 1을 추가하고, 내려오면서 계속 * 2를 해준 결과를 더하는 식으로 대강 구현하면 쉽게 풀릴 것 같았습니다. Stack으로 풀면 O(N)만에 가능하므로 충분히 이게 정해일 것이라 판단하였습니다. 그런데, 이렇게 풀면 모든 서브태스크를 맞출 수 없었습니다.

 

이후에 무엇이 틀렸는 지를 고민해보았습니다. 그러다가 "((.....()....))" 이러한 구조의 3000000 길이의 문자열을 생각해보았습니다. 결과는 2^14999999 이므로 어떤 정수형이라도 이 값을 받을 수가 없습니다. 이런 반례들 때문에 모든 서브태스크를 못 맞추었다고 판단하였습니다만, 이러한 문제가 있는걸 파악하면서 F 함수 결과값은  2^k의 합으로 이루어지므로 서로 다른 k들을 저장해서 판단하면 되겠다는 생각을 하였습니다. 저는 이를 Set을 활용해서 관리하기로 했습니다. F[a]와 F[b]를 비교할 때 k 중의 최댓값을 구하면서 비교를 해야하고,  k들을 순서대로 넣다가 이미 Set 내에 k가 있는 경우에는 k를 지우고 k+1가 있는지를 다시 확인하는 등의 작업도 해야하는데 이를 전부 O(logN)만에 가능한게 Set이기 때문입니다.

 

그래서 저는 아래와 같이 풀었습니다. 총 시간복잡도는 O(T(NlogN))이었습니다.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
// Default

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
// PBDS


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

    
    ll T;
    cin >> T;
    while(T--){
        string a, b;
        cin >> a >> b;
        
        set<ll> sa;
        set<ll> sb;
        sa.insert(0);
        sb.insert(0);

        ll depth = 0;
        bool up = true;
        for(char ch : a){
            if(ch == '('){
                depth++;
                up = true;
            }
            else {
                if(up){
                    ll tmp = depth;
                    while(sa.find(tmp) != sa.end()){
                        sa.erase(tmp);
                        ++tmp;
                    }
                    sa.insert(tmp);
                }
                up = false;
                --depth;
            }
        }

        depth = 0;
        up = true;
        for(char ch : b){
            if(ch == '('){
                depth++;
                up = true;
            }
            else {
                if(up){
                    ll tmp = depth;
                    while(sb.find(tmp) != sb.end()){
                        sb.erase(tmp);
                        ++tmp;
                    }
                    sb.insert(tmp);
                }
                up = false;
                --depth;
            }
        }
        
        
        ll max_a = *(sa.rbegin()), max_b = *(sb.rbegin());        
        while(max_a == max_b){
            if(max_a == 0 && max_b == 0) break;
            sa.erase(max_a);
            sb.erase(max_b);
            max_a = *(sa.rbegin());
            max_b = *(sb.rbegin());             
        }
        if(max_a == max_b) cout << "=\n";
        else if(max_a > max_b) cout << ">\n";
        else cout << "<\n";
        
    }

    return 0;
} // Tree_Set, Stack, Bitmasking(?)
// O(TNlogN)

풀이들을 나중에 살펴보니, 제 풀이처럼 Set을 활용하는 것보다 그냥 큰 배열을 두어 이를 관리하는게 더 빨랐다는 걸 알았습니다. 시간복잡도 상으로는 O(N)일텐데 더 빠른게 놀랍네요. 이와 별개로 2^k들의 합으로 이루어지므로 k들을 따로 관리하여 푸는 아이디어가 참 좋았던 것 같습니다.