[Python] 백준 12919 A와B 2

문제

https://www.acmicpc.net/problem/12919

입력

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

출력

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

입력 예제

A
BABA

BAAAAABAA
BAABAAAAAB

A
ABBA

출력 예제

1

1

0

문제 풀이

• s -> t가 가능한지 탐색한다면 모든 경우의 수를 탐색하게 되므로 시간초과가 발생한다. 따라서 t -> s가 가능한지 문자를 삭제해가며 탐색해야한다.
• 탐색하는 방법도 아래와 같이 뒤집어줘야한다.
  • A를 추가한다 -> A를 삭제한다.
    • 맨 뒤에 있는 A를 삭제하기 위해 아래와 같이 인덱스 슬라이싱을 진행한다.

result[:-1]

• B를 추가하고 뒤집는다 -> 뒤집은 후 B를 삭제한다.
  • B를 추가하고 뒤집은 경우 B가 맨 앞에 있을 것이므로 첫 문자를 삭제한 후, 뒤집으면 되돌릴 수 있다.

result[1:][::-1]

• 종료 조건은 두 가지로 t를 s로 만든 경우(성공), 현재 만들고 있는 단어의 길이가 s보다 짧은 경우(실패)이다.

실패 코드 (s -> t)

s = input()
t = input()
result = s
length = len(t)
res = 0
def make_t(result):
    global res
    # 종료조건
    if result == t:
        res = 1
        return 1

    if len(result) == length:
        # print(0)
        return 0

    make_t(result+'A')
    tmp = result + 'B'
    tmp = tmp[::-1]
    make_t(tmp)


make_t(result)
print(res)

정답 코드 (t -> s)

s = input()
t = input()
length = len(s)
res = 0

# t -> s
def make_t(result):
    global res
    # 종료조건
    if result == s:
        res = 1
        return

    if len(result) < length:
        return

    # A 없애기
    if result[-1] == 'A':
        make_t(result[:-1])

    # 뒤집고 B 없애기
    if result[0] == 'B':
        make_t(result[1:][::-1])


make_t(t)
print(res)