문제

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

풀이

첫 번째 접근

주어지는 문자열 S로 부터 두 가지 연산의 경우에 따라 분기하는 재귀 함수를 만들어 풀었다. 뒤를 붙여나가면서 진행했더니 메모리 초과가 났다. T와 같아지는지를 중간에 판별할 수 없어 끝까지 살펴봐야해서 메모리 초과가 난다고 생각을 했다.

두 번째 접근

거꾸로 접근하는 방법을 생각해보았다.
현재 문자열이 'A'로 끝난다면 그 전 문자열에서 'A'를 뒤에 추가한 것이므로 'A'를 떼준다.

현재 문자열이 'B'로 시작한다면 그 전 문자열에서 'B'를 뒤에 추가하고 뒤집은 것이므로 현재 문자열을 뒤집고 맨 뒤 'B'를 떼준다.

만약 두 가지 경우를 만족하지 않은 경우라면 S가 T로 변환될 수 없는 경우가 될 것이다.

예제 입력 3을 살펴보면 알 수 있다.
S = 'A'

T = 'ABBA'

T 는 우선 'A'로 끝나므로 뒤를 떼어준다.
-> T = 'ABB'

T 는 'A' 로 끝나지도 'B'로 시작하지도 않는다. 이 말은 주어진 두 가지 조건에 의해 생성될 수 없는 문자열임을 뜻한다.

따라서 예제출력이 0임을 알 수 있다.

CODE

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**8)


def solve():
    s = str(input().rstrip())
    target = str(input().rstrip())
    n = len(s)

    def recur(word):
        x = len(word)
        if x == n:
            if word == s:
                print(1)
                exit(0)
            return

        st, ed = word[0], word[x-1]

        if ed == 'A':
            recur(word[:x-1])

        if st == 'B':
            recur(word[::-1][:x-1])

    recur(target)
    print(0)


solve()

이전에 봤던 문자열을 따로 체크해준다면 시간을 조금 더 줄일 수 있다.

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**8)


def solve():
    s = str(input().rstrip())
    target = str(input().rstrip())
    n = len(s)
    dic = {}
    
    def recur(word):
        x = len(word)
        if x == n:
            if word == s:
                print(1)
                exit(0)
            return

        st, ed = word[0], word[x-1]

        if ed == 'A' and not dic.get(word[:x-1]):
            dic[word[:x-1]] = 1
            recur(word[:x-1])

        if st == 'B' and not dic.get(word[::-1][:x-1]):
            dic[word[::-1][:x-1]] = 1
            recur(word[::-1][:x-1])

    recur(target)
    print(0)


solve()