[BOJ] 12919 - A와 B 2

접근

문자열 S로부터 주어진 연산을 통해 T를 만들어낼 수 있는지를 판단하여야 한다.

1. 문자열 뒤에 'A'를 추가한다.
2. 문자열 뒤에 'B'를 추가하고 문자열을 뒤집는다.

원본 문자열 S로부터 결과 문자열 T를 찾아내는 방법보다 T에서 S를 만들어낼 수 있는지 확인하는 것이 더 효율적이라고 할 수 있다.

즉, 역으로 문자열 T로부터

1. 문자열 T 뒤에 있는 'A'를 제거한다.
2. 문자열 T 앞에 있는 'B'를 제거하고 문자열을 뒤집는다.

로 문제를 바꾸어 생각해보는 것이다.

또한 모든 경우를 살펴보면 문자열 T는 다음과 같은 경우들로 나눌 수 있다는 것을 알 수 있다.

(X ----- Y는 X로 시작해서 Y로 끝나는 문자열을 의미한다.)

1. A ----- A
2. A ----- B
3. B ----- A
4. B ----- B

1번의 경우 꼬리에 있는 문자 'A'를 지울 수 있다.
2번의 경우 할 수 있는 연산이 없다.
3번의 경우 꼬리에 있는 문자 'A'를 지울 수 있고, 머리에 있는 문자 'B'를 지울 수 있다.
4번의 경우 머리에 있는 문자 'B'를 지울 수 있다.

이를 좀 더 간소화하면
A --- *의 경우 꼬리의 문자가 'B'가 될 때까지 꼬리에 있는 문자 'A'를 지운다.
B --- *의 경우 머리의 문자 'B'를 지울 수 있다. 이 때 꼬리의 문자가 'A'인 경우 그것도 지울 수 있다.

위의 규칙을 그대로 코드로 구현해보자.

코드

from sys import stdin
from collections import deque

res = 0
S, T = tuple(stdin.readline().strip() for _ in range(2))

def find(str_, rev):
    global res

    # 종료 조건
    if len(S) == len(str_):
        if rev:
            str_.reverse()
        # 정답 조건
        if S == "".join(str_):
            res = 1
        return

    t = deque(str_) # 복사본 생성

    head = 0 if not rev else -1
    tail = -1 if not rev else 0

    if t[head] == 'A': # A----*
        while t[tail] != 'B' and len(S) < len(t): # A----A인 경우
            del t[tail] # 맨 뒤에 있는 'A' 제거
        
        # A-----B 또는 종료 조건을 달성한 A---A
        if len(S) == len(t):
            if rev:
                t.reverse()
            if S == "".join(t):
                res = 1

        # 이 문자열로는 더이상 할 것이 없음
        return

    # B-----*
    if t[tail] == 'A': # B-----A인 경우
        t_ = deque(t) # 복사본 생성
        del t_[tail] # 맨 뒤에 있는 'A' 제거
        find(t_, rev) # 수정한 문자열로 탐색

    # 맨 앞의 'B' 제거
    del t[head]
    rev = not rev # 문자열 뒤집기
    find(t, rev) # 수정된 문자열로 탐색

find(T, False)
print(res)

find 함수에서 매개변수 str_을 그대로 사용하지 않고 별도 변수 t에 복사하여 사용하는 이유는 파이썬에서 함수의 매개변수가 전달되는 방법이 passed by assignment이며, 또 리스트를 복사할 때 기본적으로 얕은 복사가 진행되기 때문인데, 이에 대한 자세한 이야기는 다음에 별도의 포스팅으로 다뤄보겠다.

... 사실 B를 제거할 때 rev와 같은 상태 변수에 표시만 하지 않고 문자열을 진짜 뒤집어도(String.reverse()) 이 문제에서는 소요 시간 차이가 없었다. 이는 주어진 문자열의 길이가 그렇게 길지 않아서(<=50)인 것이며 String.reverse()의 시간복잡도는 $O(n)$이므로, 주어지는 문자열의 길이 $N$이 커지면 소요 시간 차이는 그만큼 커질 수 밖에 없다. 다만 문자열을 직접 뒤집으면 구현에 있어 훨씬 간단명료해지므로 이 문제와 같이 $N$이 적당한 상황에서는 좋은 방법이라고 할 수 있다.