백준 12919 A와 B 2 Python

🐸 문제 정보

12919번: A와 B 2

 

🤖 알고리즘

백트래킹

 

⏱️ 풀이 시간

20.06m

 

📝 풀이

이 문제의 핵심은 S -> T가 아닌, T -> S로 가야한다는 점이었다.

처음에 S -> T로 가는 백트래킹 코드로 시간초과가 났지만, 같은 로직의 T -> S로 가는 함수를 작성하여 통과할 수 있었다.

 

S -> T의 경우, 두 문자열을 비교한다고는 하지만 T로 가며 무한으로 발산되는 형태임에 반해

T -> S의 경우, 문자을 하나씩 지우기 때문에 0으로 수렴하는 형태이기 때문임을 알 수 있었다.

 

1. 맨 뒤가 A면, A빼서 넘기기
2. 맨 앞이 B면, 배열을 뒤집고 맨 뒤의 B를 빼서 넘기기

이때 넘기는 배열은 복사해서 넘겨야하기 때문에 슬라이싱을 이용했다.

배열을 뒤집는 경우에도, reversed가 슬라이싱보다 근소하게 빠르지만 이 경우에는 슬라이싱을 이용하는 것이 옳다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

s = list(input().rstrip())
t = list(input().rstrip())

def bt(arr):
    global res
    if len(s) == len(arr):
        if s == arr:
            print(1)
            exit()
        return
    if arr[-1] == 'A':
        bt(arr[:-1])
    if arr[0] == 'B':
        bt(arr[::-1][:-1])

bt(t)
print(0)