[문자열] Python - 12904번, A와 B

www.acmicpc.net/problem/12904

S = list(input())
T = list(input())

lenS = len(S)
while lenS < len(T):
    if T[-1] == 'A':
        T.pop()
    else:
        T.pop()
        T = T[::-1]
if T == S:
    print(1)
else:
    print(0)

무조건 S -> T로 bfs를 이용해서 풀고자 하였는데, 아무리 시간 복잡도를 줄여도 소용이 없었다.

실은, 특정 문자열을 얻기 위한 방법이 오로지 하나였다. 그렇지 않은 줄 알고 많은 경우를 고려하려고 하였던 것이다.

 

풀이법은 간단하다. T의 마지막 문자에 따라서, A만 없애거나, B를 없애고 뒤집거나, 둘 중 하나의 연산을 해주고, T가 결국 S의 길이와 같게 되면 비교를 해주는 것이다.