(C++) - 백준(BOJ) 12904번 : A와 B

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

12904번: A와 B

반대로 생각해야하는 문자열 처리문제였습니다.

 

풀이방법

 A를 추가하거나 뒤지고 B를 추가하여 t를 만드는데 brute force를 생각할 수 있으나 매번 2배씩 분기되기 때문에 2의 1000(문자열 최대길이)승 정도의 시간복잡도로 시간초과가 납니다. 

 

1. 생각전환 : 반대로 생각하면 풀립니다. t->s로 문자를 만든다고 생각해봅니다. 이를 만드는데는 2가지 조건이 있습니다. 

 1-1. t의 가장 마지막 문자가 'A'라면 해당 문자를 지워줍니다.

 1-2. 'B'인 경우도 지워준 후 역순을 취합니다.

이 방식으로 s와 size가 같아질때까지 loop를 돌린 후 s와 t를 비교합니다.

 

2. 답 출력 : s == t라면 1 아니라면 0을 출력합니다.

 답을 찾는데 꼭 문제에 나와있는 조건을 그대로 구현해 시뮬레이션할 필요가 없었던, 발상의 전환을 요했던 문제였습니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
string s,t,ans;
int main(){
    cin >> s >> t;
    while(s.size() != t.size()){
        if(t[t.size()-1] == 'A') t.pop_back();
        else{
            t.pop_back();
            reverse(t.begin(),t.end());
        }
    }
    if(s != t) cout << 0 << '\n';
    else cout << 1 << '\n';
}