Codeforces #1494A ABC String

문제

https://codeforces.com/problemset/problem/1494/A

걸린 시간

-

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        string a;
        cin >> a;
        bool regular = false;
        for(int mask = 1; mask <= 6; mask++){
            stack<int> s;
            for(char c : a){
                int b = 1<<c-'A';
                if(mask & b) s.push(b);
                else{
                    if(s.empty()) s.push(b);
                    else{
                        if((mask & s.top()) ^ (mask & b)) s.pop();
                        else s.push(b);
                    }
                }
            }
            if(s.empty()) regular = true;
        }
        if(regular) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

처음 문제를 풀 땐 무식하게 코드를 작성했지만 bitmask 기법을 이용하면 가능한 2³ 개의 경우의 수를 깔끔하게 관리할 수 있었다.

현재 단어가 닫는 괄호인지 여는 괄호인지를 mask 와의 and 연산을 통해 확인하고, 스택의 맨 위에 있는 값과 xor 연산을 통해 괄호의 쌍이 일치하는지를 검사하면 된다.