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 |
댓글