[백준/Python] 12904 A와 B

문제 링크

12904번: A와 B

 

문제 풀이

• 처음에는 큐를 생성하고 s를 넣은 상태에서 A, B를 더해서 다시 큐에 넣어서 t와 비교하는 방식으로 접근하였다. 하지만, 메모리 초과가 발생해서 게시판의 질문들을 통해서 힌트를 조금 얻었다.
• 먼저, s를 t로 만들게 되면, 그 경우의 수가 많아지게 된다는 것이다. 이때, t의 길이가 될 때까지 진행해야 하므로 당연히 s와 t의 길이 차가 많이 날수록 그만큼 큐에 들어있는 문자열 또한 많아지게 된다.
• 반대로 생각하면, t를 s로 만드는 것이다. A, B를 더해서 새로운 문자열이 만들어지므로, t의 마지막 문자에 따라 기존의 문자열이 무엇이었는지 확인할 수 있다.
• 이를 길이가 s와 동일할때까지 반복해서 진행하면 원래의 문자열이 나오고, s와 비교하였을 때, 동일한 값이면 1을 출력하고, 아니면 0을 출력하는 간단한 문제가 된다.

 

전체 코드

import sys

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

while len(t) > len(s):
    if t[-1] == "A":
        t = t[:-1]
    else:
        t = t[:-1][::-1]

if t == s:
    print(1)
else:
    print(0)