백준 12904 - A와 B (greedy)

문제 : 12904번: A와 B (acmicpc.net)

12904번: A와 B

 

풀이과정

문자열 S를 2가지 규칙에 의해 T로 바꿀 수 있는지 물어보는 문제였습니다.

 

만약 S -> T로 변환하려고 한다면 최악의 경우 2^N만큼의 반복이 필요하기 때문에

시간복잡도가 O(2^N) 이 되어서 시간 내에 풀기 어렵습니다.

 

그러나 역방향으로 T -> S로 변환한다고 하면

1) 마지막 문자가 A인 경우 A를 삭제

2) 마지막 문자가 B인 경우 B를 삭제하고 reverse

2가지 과정이 정해지기 때문에 시간복잡도가 O(N)이 됩니다.

 

기저사례로 S와 T의 길이가 같아졌을 때 문자가 같은지 비교하면 해결할 수 있었습니다.

코드

#include <iostream>
#include <vector>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
string S,T;

/*
    길이가 긴 문자열 -> 짧은 문자열로 변환하는 과정은 O(n) 의 시간복잡도가 걸린다
    반면 짧은 -> 긴 문자열 변환은 O(2^n)의 지수함수 시간복잡도가 걸린다
*/

int solution() {
    while(1) {
        // 기저사례
        if(S.length() == T.length()) {
            if(S == T) return 1;
            else return 0;
        }

        // 맨 뒤가 A인경우 제거
        if(T.back() == 'A')
            T.pop_back();
        // B인경우 제거하고 뒤집기
        else if(T.back() == 'B') {
            T.pop_back();
            reverse(T.begin(),T.end());
        }
    }
}
int main()
{

    cin >> S;
    cin >> T;
    printf("%d\n",solution());
}