[baekjoon] 백준 12919번(파이썬): A와 B 2

문제

12919번: A와 B 2

알고리즘

- 백 트래킹을 통해 완성된 문자열로 시작 문자열을 만들 수 있는지 확인한다.

- 백 트래킹은 2가지 조건을 통해 수행한다.

코드

import sys


# 백 트래킹을 통해 완성된 문자열로 시작 문자열을 만들 수 있는지 확인
def solution(c):
    global flag

    if len(c) == len(s):
        if c == s:
            flag = True

        return

    if c[0] == "B":
        c.reverse()
        c.pop()
        solution(c) # 백 트래킹
        c.append("B")
        c.reverse()

    if c[-1] == "A":
        c.pop()
        solution(c) # 백 트래킹
        c.append("A")


s = list(map(str, sys.stdin.readline().strip()))
t = list(map(str, sys.stdin.readline().strip()))
flag = False
solution(t)

if flag:
    print(1)
else:
    print(0)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법