A와 B

출처 : 백준 #12904

시간 제한	메모리 제한
2초	512MB

---

문제

수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

• 문자열의 뒤에 A를 추가한다.
• 문자열을 뒤집고 뒤에 B를 추가한다.
  주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.

---

입력

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)

---

출력

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

---

입출력 예시

예제 입력 1

B
ABBA

예제 출력 1

1

---

예제 입력 2

AB
ABB

예제 출력 2

0

---

풀이

생각 및 풀이 설명

• 처음에는 첫 번째로 주어진 문자열(S)을 두 번째 문자열(T)로 바꾸려고 했다.
• 그러다 보니 아래의 이미지와 같이 고려해야 할 사항이 엄청 증가했다.
• 한 글자가 늘어날 때마다 약 2배씩 증가하는 모습을 보였다.(중간에 가지치기를 하더라도.. )
• 따라서 처음 풀었던 풀이는 당연하게도 메모리 초과가 나타났다.

• 메모리 초과가 이해가 잘 안된다면 주어진 문자열 S의 길이가 1이고, T의 길이가 1000이라고 생각해보면 된다.
• 만약 모든 경우를 고려한다고 하면 O(2^N)의 공간 복잡도가 생긴다...

python code (처음 풀이 S->T)

# 백준 12904번 A와 B
from sys import stdin
from collections import deque
input = stdin.readline

S = input().rstrip()
T = input().rstrip()

def solution(T, S):
    n = len(T) - len(S)

    S_a, S_b, T_a, T_b = 0, 0, 0, 0
    for s in S:
        if s == "A":
            S_a += 1
        else:
            S_b += 1
    
    for t in T:
        if t == "A":
            T_a += 1
        else:
            T_b += 1

    result = deque([(S, 0, S_a, S_b)])
    while result:
        now, count, sa, sb = result.popleft()
        if len(now) != len(T):
            if count % 2 == 0:  # 짝수번 뒤집힌 상태
                a = now + "A"
                b = "B" + now
            else:               # 홀수번 뒤집힌 상태
                a = "A" + now
                b = now + "B"

            if sa < T_a:
                result.append((a, count, sa+1, sb))
            if sb < T_b:
                result.append((b, count+1, sa, sb+1))
        else:
            if count % 2 == 0:
                if now == T:
                    return 1
            else:
                if now[::-1] == T:
                    return 1
    return 0

print(solution(T, S))

• 따라서 생각을 달리할 필요가 있었다.
• 처음에는 계속 S->T로 바꿔야 한다는 고정관념 때문에 어떻게 공간복잡도를 줄일 수 있을지 몰랐다.
• 시도를 하더라도 최악의 경우에 공간복잡도에는 변화가 없었다.
• 따라서 반대로 T->S로 바꾸기로 결정했다.
• 이대로 하면 쓸데없이 공간을 차지하지 않고 시간안에 탐색이 가능했다.

python code (두 번째 풀이 T->S)

# 백준 12904번 A와 B
from sys import stdin
from collections import deque
input = stdin.readline

S = input().rstrip()
T = input().rstrip()

def solution(T, S):
    while T != S:
        if T[-1] == "A":
            T = T[:-1]
        else:
            T = T[::-1][1:]
        # print(T)

        if len(T) <= len(S):
            if T == S:
                return 1
            else:
                return 0
    return 1

print(solution(T, S))