[백준/Python] 12919 - A와 B 2

문제

수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

문자열의 뒤에 A를 추가한다.
문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.
주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 49, 2 ≤ T의 길이 ≤ 50, S의 길이 < T의 길이)

출력

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

풀이
처음에는 문제 그대로 구현할 생각에 감이 아예 안잡혀서 고민하다 다른 분의 풀이에 힌트를 얻었다
정말 어떻게 이런 아이디어를 떠올리지 .........

방법은 간단하게 문제에서 제시한 방식을 반대로 이행한다

맨 뒤에 A를 붙였다면 맨 뒤에있는 A를 제거하고
맨 뒤에 B를 붙이고 문자열을 뒤집었다면 문자열을 뒤집어서 B를 제거한다

처음에는 while문으로도 구현할 수 있을 것이라 생각해서 구현했었는데, 한번 A인지 검사하는 분기를 지나고나면 마지막에 오는 문자가 또 다시 A인 경우는 체크할 수 없어서 문제가 된다
따라서 재귀를 사용해야한다 맨 뒤에 A가 오는 경우에 A를 제거한 후 재귀함수를 호출하고, 맨 앞에 B가 오는 경우에는 B를 제거하고 문자열을 다시 뒤집은 후에 재귀함수를 호출한다
B일 때 맨 앞을 체크하는 이유는 본래 과정에서 맨 뒤에 B를 추가하고 문자열을 뒤집기 때문에 추가한 B가 맨 앞자리에 위치해있기 때문이다
그리고 문자열을 매 호출마다 s와 비교하여 동일한지 체크하고 동일하면 1을 프린트한 후 프로그램을 종료한다
문자열 t가 빈 문자열이 되면 인덱스 에러가 발생할 것이고, s와 t가 같지 않음을 의미하므로 함수를 리턴한다

정답 코드

import sys

s = sys.stdin.readline().strip()
t = sys.stdin.readline().strip()

def transform(t):
    if t == s:
        print(1)
        sys.exit()
        
    if len(t) == 0:
        return

    if t[-1] == "A":
        transform(t[:-1])
    if t[0] == "B":
        transform(t[1:][::-1])
        
transform(t)
print(0)