20955. XY 문자열 1 (SWEA)

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

출처:

SW Expert Academy

나의 풀이

from collections import deque
T = int(input())
 
for test_case in range(1, T + 1):
    S=input()
    E=input()
    while len(S)<len(E):
        if E[-1]=='X':
            E=E[:-1]
        else:
            E=E[:-1]
            E=E[::-1]
    if S==E:
        print(f'#{test_case} Yes')
    else:
        print(f'#{test_case} No')

• 처음에는 BFS나 DFS 또는 Backtracking으로 풀까 했는데, 연산량이 너무 많아서 다른 방법을 생각했다.
• E는 마지막이 X면 없애거나, Y이면 없애고 뒤집는 2가지 연산을 할 수 있고, 이는 선택사항이 아니다. 즉 맨 뒤가 X면 2번째 연산은 할 수 없는 것이다.
• 따라서 E에 가능한 연산을 하고, S가 만들어지만 Yes이고, 만들어지지 않으면 No인 것이다.