[백준][C++] 12904 A와 B

www.acmicpc.net/problem/12904

12904번: A와 B

 

 

 

알고리즘 종류

    - 구현

 

 

 

사고 과정

    - S 문자열이 T 문자열이 될 수 있는지 확인하는 문제이다. S에서 T가 되도록 DFS를 사용하면 경우의 수가 많아져서 시간초과가 발생한다. 하지만, T에서 S로 역방향을 해준다면 시간복잡도가 O(n)이라서 빠르게 할 수 있다.

    - T 문자열 뒤에서 부터 하나씩 확인하며 빼거나 뒤집는다.

 

 

구현(C++)

#include <iostream>
#include <string>
#include <algorithm> 
 
using namespace std;
 
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    string s, t;
    cin >> s >> t;
    
    while(true){
        
        if(s.length() == t.length()){
            if(s == t) cout << 1;
            else cout << 0;
            break;
        }
        
        if(t[t.size()-1] == 'A'){
            t.pop_back();
        }
        else if(t[t.size()-1] == 'B'){
            t.pop_back();
            reverse(t.begin(), t.end());
        }
    }
}

 

 

 

시행착오

    - 처음에 S에서 T로 만드는 동작으로 구현했다. 시간초과가 발생했다. 도저히 아이디어가 떠오르지 않아서 조사해보니, T에서 S로 역방향으로 동작하는 방법을 알게 되었다. 문제의 의도인 '확인'이기 때문에 사용할 수 있는 방법 같았다. 만약에 S에서 n길이로 만들고, 만들어진 것에서 최솟값/최댓값 같은 것을 구해야 하다면, DFS로 하는 것이 맞아 보인다.

 

    - string 거꾸로 만들 때, <algorithm>에서 reverse()를 사용하면 된다는 것을 배울 수 있었다. 

    - string을 vector처럼 사용할 수 있다. begin(), end(), pop_back()이 가능했다.