백준 12919 A와 B 2 / C++

문제 : 12919

풀이 point

문자열 s와 t를 입력받는데 s를 t로 만드는 것은 경우의 수가 굉장히 많다.
그렇기 떄문에 시간초과가 발생할 것이므로 다른 방법을 생각해야한다.

다른 방법은 t를 s로 만드는 것이다. t를 s로 만들기 위한 패턴은
1. t의 맨 끝이 A라면 A를 지운다.
2. t의 맨 앞이 B라면 B를 지우고 문자열을 뒤집는다.

이 방법을 통해 s가 t가 될 수 있음을 찾을 수 있다.

풀이 방법

패턴을 구현한다. 이때 주의할 점이 있다. 인자로 넘겨주는 문자열이 원 문자열을 복사하여 A를 지우거나 B를 지우고 뒤집은 복사본이어야 한다. 복사본에 패턴을 적용하는 것이 아닌 원 문자열에 패턴을 적용한 값을 넘겨주면 단 한 가지 경우의 수만 보는 것이다.

여러가지의 경우의 수를 볼 수 있도록 복사본을 넘겨야한다.
재귀가 진행되면서 다양한 경우의 수를 탐색 후 답 문자열이 s와 같아진다면 return 해주면 된다.

풀이 코드

//백준 12919, A와 B 2

#include <iostream>
#include <algorithm>

std::string s, t;
bool flag = false;

void recur(std::string ans){
    if(ans == s){
        flag = true;
        return;
    }
    if(s.size() >= ans.size()) return;
    if(ans.back() == 'A'){
        recur(ans.substr(0, ans.size()-1));
    }
    if(ans.front() == 'B'){
        auto tmp = ans.substr(1);
        std::reverse(tmp.begin(), tmp.end());
        recur(tmp);
    }
}

int main(){

    std::cin >> s;
    std::cin >> t;
    recur(t);
    std::cout << (flag ? 1 : 0);
    return 0;
}

사족

s를 t로만 만들려고 시작했는데 아무래도 시간복잡도를 봤으면 다른 방법을 생각해냈을 것 같다. 시간복잡도를 생각하지 못한 것이 아쉽다. 도저히 백트래킹 + 시간이 오래 걸려 재귀로는 할 수 없다고 생각한 후 힌트를 봤더니 "아 이런거구나..." 싶었다.
다음부터는 재귀 구현에만 신경쓰지 말고 실전 문제를 풀듯이 시간복잡도를 생각해야겠다.