A. ABC String

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 reqular = false;
        stack<char> s;
        // a <- b, a <- c
        for(char c : a){
            if(s.empty()){
                s.push(c);
            }
            else{
                switch(c){
                    case 'A':
                        s.push(c);
                        break;
                    case 'B':
                        if(s.top() == 'A') s.pop();
                        else s.push(c);
                        break;
                    case 'C':
                        if(s.top() == 'A') s.pop();
                        else s.push(c);
                        break;
                }
            }
        }
        if(s.empty()) reqular = true;
        while(!s.empty()) s.pop();
        // b <- a, b <- c
        for(char c : a){
            if(s.empty()){
                s.push(c);
            }
            else{
                switch(c){
                    case 'A':
                        if(s.top() == 'B') s.pop();
                        else s.push(c);
                        break;
                    case 'B':
                        s.push(c);
                        break;
                    case 'C':
                        if(s.top() == 'B') s.pop();
                        else s.push(c);
                        break;
                }
            }
        }
        if(s.empty()) reqular = true;
        while(!s.empty()) s.pop();
        // c <- a, c <- b
        for(char c : a){
            if(s.empty()){
                s.push(c);
            }
            else{
                switch(c){
                    case 'A':
                        if(s.top() == 'C') s.pop();
                        else s.push(c);
                        break;
                    case 'B':
                        if(s.top() == 'C') s.pop();
                        else s.push(c);
                        break;
                    case 'C':
                        s.push(c);
                        break;
                }
            }
        }
        if(s.empty()) reqular = true;
        while(!s.empty()) s.pop();
        // a <- c, b <- c
        for(char c : a){
            if(s.empty()){
                s.push(c);
            }
            else{
                switch(c){
                    case 'A':
                        s.push(c);
                        break;
                    case 'B':
                        s.push(c);
                        break;
                    case 'C':
                        if(s.top() == 'A' || s.top() == 'B') s.pop();
                        else s.push(c);
                        break;
                }
            }
        }
        if(s.empty()) reqular = true;
        while(!s.empty()) s.pop();
        // b <- a, c <- a
        for(char c : a){
            if(s.empty()){
                s.push(c);
            }
            else{
                switch(c){
                    case 'A':
                        if(s.top() == 'B' || s.top() == 'C') s.pop();
                        else s.push(c);
                        break;
                    case 'B':
                        s.push(c);
                        break;
                    case 'C':
                        s.push(c);
                        break;
                }
            }
        }
        if(s.empty()) reqular = true;
        while(!s.empty()) s.pop();
        // a <- b, c <- b
        for(char c : a){
            if(s.empty()){
                s.push(c);
            }
            else{
                switch(c){
                    case 'A':
                        s.push(c);
                        break;
                    case 'B':
                        if(s.top() == 'A' || s.top() == 'C') s.pop();
                        else s.push(c);
                        break;
                    case 'C':
                        s.push(c);
                        break;
                }
            }
        }
        if(s.empty()) reqular = true;
        if(reqular) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

A,B,C 3개의 단어로 이루어진 문자열이 주어진다. 각각의 단어를 괄호로 생각했을 때 모든 괄호의 쌍이 일치하는 경우를 regular 하다고 한다. 문제는 주어진 문자열이 regular 할 수 있는지 여부를 묻고 있다.

괄호는 여는 괄호, 닫는 괄호 두 가지가 있다. 총 경우의 수는 23 으로 8가지가 나오게 되는데, 괄호의 종류가 모두 같은 경우는 절대 regular 할 수 없으므로 두 가지를 제외한 6가지 경우만 스택을 이용해 검사해주면 ac 를 받을 수 있다.

후기

독해에는 시간이 많이 걸리지 않았지만 B, C번 문제의 풀이가 잘 떠오르지 않았다. 다음번에는 2문제를 푸는 것을 목표로 해야겠다.

'Codeforces' 카테고리의 다른 글

Codeforces #1494B Berland Crossword  (0) 2021.03.04
Codeforces #1494A ABC String  (0) 2021.03.04
Codeforces #1485A Add and Divide  (0) 2021.03.02
Codeforces #1491A K-th Largest Value  (0) 2021.03.02
Codeforces #1486A Shifting Stacks  (0) 2021.03.01

댓글