[백준 12904] A와 B

A와 B

문제 설명

시작하는 문자열 S와 만들고자 하는 문자열 T를 입력 받은 뒤, 규칙을 지켜서 T로 만들 수 있으면 1을 출력하고 그렇지 않으면 S를 출력한다.

그 규칙은 다음과 같다.

1. 문자열의 뒤에 A를 추가한다.
2. 문자열을 뒤집고 뒤에 B를 추가한다.

---

알고리즘

1. S와 T를 입력 받는다.
2. 반복문을 통해서 T를 맨 뒤 글자부터 확인한다.
3. 맨뒤가 A인 경우 맨 뒤 한 글자를 지운다.
4. 맨뒤가 B인 경우 맨 뒤 한 글자를 지우고 뒤집는다.
5. 반복문에서 S의 길이와 T의 길이가 같은 경우 반복을 멈춘다.
6. S와 T를 비교해서 같으면 1 다르면 0을 출력시킨다.

정답 코드

#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    string S, T;    
    cin >> S >>T;

    while(1)
    {
        if (T.length() == S.length())//길이가 같아지면 중단
            break;
        if (T[T.length()-1] == 'A')//T의 맨 끝 글자가 A이면 지우기
            T=T.substr(0, T.length() - 1);
        else if (T[T.length() - 1] == 'B')//T의 맨 끝 글자가 B이면 지우고 뒤집기
        {
            T=T.substr(0, T.length() - 1);
            reverse(T.begin(), T.end());
        }        
    }
    if (S == T)//T를 지워서 결과적으로 S와 동일하면 만들 수 있음
        cout << 1;
    else//만들 수 없는 경우
        cout << 0;

    return 0;
}

고찰
처음에는 S를 T로 만드는 방식으로 구현했다. 테스트 케이스는 전부 답이 출력 되어서 제대로 되는 줄 알았는데 안되는 케이스가 있었다. 아래와 같이 코드를 작성했다.

#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    string S, T;

    cin >> S >>T;
    string temp(S);
    int size = S.length() + 1;
    for (int i = S.length(); i < T.length();i++)
    {
        string cmp = T.substr(T.length()-size,size);//문자열의 뒷부분 추출
        temp += 'A';
        if (temp == cmp)//같으면 붙여도 됨
        {
            size++;
            continue;
        }
        else
            temp=temp.substr(0,temp.length()-1);

        reverse(temp.begin(), temp.end());//문자열 뒤집기
        cmp = T.substr(T.length() - size, size);//문자열의 앞부분 추출 -> 뒤집었기 때문
        temp += 'B';    

        if (temp != cmp)//두 방법 다 안되면 만들 수 없다는 의미
            break;
    }
    if (temp == T)
        cout<< 1;
    else
        cout<< 0;

    return 0;
}

테스트 케이스는 잘 돌아간다. 하지만 문제점은 S=A, T=BABA와 같이 한 글자를 뒤집는 경우를 따로 고려해줘야해서 코드가 매우 복잡해지고 길어질 수 밖에없다.
그리디 알고리즘 부분을 공부의 필요성을 느꼈던 예제였다.