Baekjoon [12919] A와 B 2 - python

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

12919번: A와 B 2

 

처음 문제를 봤을때 S에서 T로 만드는 것은 힘들 것이라 생각하여 T를 S로 만들자 생각했다.

 

틀린코드

original_text = list(input())
target_text = list(input())
gap = len(target_text) - len(original_text)
for i in range(gap):
    if target_text[0] == "A":
        target_text = target_text[1:]
        # print(target_text)
    elif target_text[0] == "B":
        target_text = target_text[1:]
        target_text = target_text[::-1]
        # print(target_text)


if original_text == target_text:
    print(1)
else:
    print(0)

 

사실 위와같이 접근을 시작했는데, 주어진 테스트케이스는 통과하지만 에러가 나는 경우가 발생했다.  그 이유는 BAA와 같이

AA문자열에서 B를 만나 BAA가 됐을수도있고, BA문자열에서 A를 만나 BAA가 되는 경우도 발생했다. 이를 통해 백트래킹과 같이 함수를 통해 알고리즘을 구현하기로 진행했다.

맞는코드

import sys
original_text = list(input())
target_text = list(input())

def check(t): # 문자열 T 리스트를 입력받아
    if t==original_text:
        print(1)
        sys.exit()
    if len(t)==0:
        return 0
    if t[-1]=='A': # 마지막이 A이면
        check(t[:-1]) # 제거해서 재귀
    if t[0]=='B': # 처음이 B이면
        check(t[1:][::-1]) # B제거하고, 뒤집어서 재귀
check(target_text)
print(0)

 

위와 같이 접근하면서 다중적으로 조건을 걸어 한번에 처리하도록 진행했다.