📜 문제 이해하기
수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.
이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.
문자열의 뒤에 A를 추가한다.
문자열을 뒤집고 뒤에 B를 추가한다.
주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.
💡 문제 재정의
S에 두 가지 메소드를 이용해서 T를 만들 수 있는지 출력하라.
✏️ 계획 수립
처음 접근 방법은 문제를 있는 그대로 브루트포스로 구현하였다.
재귀 함수를 통해서 1) 문자열의 뒤에 A를 추가한것과 2) 문자열을 뒤집고 뒤에 B를 추가한 것을
재귀적으로 반복하면서 문자열이 나오는지 확인하면 된다.
하지만 위의 방법은 시간복잡도에서 문제가 발생한다.
글자가 하나씩 증가할때마다 2가지 방법을 반복하고 이는 O(2ⁿ)이 된다.
문자열의 최대 길이는 1000까지이므로 브루트포스로는 절대 해결할 수 없다.
두번째 접근 방법으로는 반대로 생각해보는 것이었다.
S부터 접근하는것이 아닌 T부터 접근하는 방법이다.
위의 메소드를 반대로 실행해보면서 가능한 것을 찾아보는 방식이다.
재귀 함수를 통해서 1) 문자열의 뒤에서 A를 빼는 것과 2) B를 빼고 문자열을 뒤집는 것을 재귀적으로 반복하는 것이다.
만약 1)에서 T문자열에 맨 뒤가 A가 아니라면 불가능한 것이고 2)에서 T문자열의 맨 뒤가 B가 아니라면 불가능하다.
문자열은 A와 B로 이루어져있기에 항상 1아니면 2를 만족하고 위의 과정을 재귀적으로 반복하다가 S가 T보다 길어진다면 탐색 실패이고 만약 S와 T가 같아진다면 반대로 S로 T를 만들 수 있다.
💻 계획 수행
def recursive_func(s, t):
# 기저 사례 1: s가 t보다 길다면 False
if len(s) > len(t):
return False
# 기저 사례 2: s와 t가 같다면 True
if s == t:
return True
if t[-1] == "A":
t = t[:-1]
elif t[-1] == "B":
t = t[:-1]
t = t[::-1]
return recursive_func(s, t)
if __name__ == '__main__':
S = input()
T = input()
if recursive_func(S, T):
print(1)
else:
print(0)🤔 회고
문제를 반대로 생각함으로써 해결할 수 있는 문제였다. 트리를 그려가면서 겹치는것이 없고 항상 하나의 길이 나오는 것으로 보고 반대로 생각할 수 있게 되었다.
