[백준] 12904 A와B

✔️ 문제 링크

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

💡핵심 아이디어

1️⃣ 길이가 짧은 문자열을 만들어서 긴 문자열을 방법을 모두 고려하면 시간복잡도는$O(2^n)$임으로 이 방법은 좋은 방법이 아니다.

2️⃣ 거꾸로 생각하여 긴 문자열을 짧은 문자열을 만드는 방법은 $O(n)$임으로 훨씬 좋은 방법이고 규칙을 다음과 같이 설정하여 길이를 줄여나가며 T의 길이가 S의 길이만큼 줄여나가며 만들 수 있는지 확인한다.
줄여나가는 규칙
1, 맨 뒤의 A를 제거
2, B를 제거하고 문자열을 뒤집음

⭐️ 소스 코드

if __name__ == '__main__':
    S = input()
    T = input()
    s_len = len(S)

    while s_len != len(T):
        if T[-1] == 'A':
            T = T[:-1]
        else:
            T = T[:-1]
            T = T[::-1]

    if T == S:
        print(1)
    else:
        print(0)