백준 12919: A와 B 2 - 재귀, 문자열(파이썬)

A와 B 2 성공

12919번: A와 B 2

문제

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

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

• 문자열의 뒤에 A를 추가한다.
• 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오. 

입력

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

출력

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

 

내 코드

import sys

def check(string):
    if len(string)==len(start): #시작 문자열과 현재 문자열 길이가 같으면 stop하고 체크.
        if string==start: #같은 문자열이면,
                return True #만들 수 있는 것임. return True;
        return False #다르면 만들 수 없는 것임. return False;

    c1=string[-1] #맨 뒤에 있는 문자(A를 찾기 위함)
    c2=string[::-1][-1] #뒤집었을 때 맨 뒤에 있는 문자(B를 찾기 위함)

    #두 케이스 모두 되는지 체크해봐야됨. (A, B에 관한 두가지)
    isOk1, isOk2=False, False #두 케이스 모두 불가능이라고 초기화
    if c1=='A':
        isOk1=check(string[:-1])
    if c2=='B':
        isOk2=check(string[::-1][:-1])

    #둘 중 하나라도 되면 만들 수 있는 것임.
    if isOk1 or isOk2:
        return True
    else:
        return False


#메인 코드 부분
start=sys.stdin.readline().rstrip()
end=sys.stdin.readline().rstrip()

if check(end):
    print(1)
else:
    print(0)

 

풀이 및 접근)

- 이런 문제와 비슷하게 특정 수에서 다른 수를 만든다던지, 특정 문자열을 다른 문자열을 만드는 문제들은, 출발->결과 로 가는 것보다

결과->출발 로 역순으로 찾아가는 것이 더 효율적이고 쉽다.

- 역순의 아이디어를 가지고 접근했다. 그러다보니 변해가는 문자열마다 모두 같은 규칙을 적용해서 문자열을 변화시키는 것이었다. 계속 같은 동작이 반복되다보니, 자연스레 재귀를 떠올렸다.

- 항상 두 규칙을 문자열에 적용해 본다. 그래서 둘 중 어느 방법으로든 최종 문자열까지 도달해서 성공 여부를 판단할 수 있다. 성공이면 True를 return하게 하였다.

- 그렇게 두 케이스에 대해 True or False를 리턴하게 해서 둘 중 하나라도 True를 리턴하면 성공으로 간주했다.

- 약간의 주의점은 두 케이스 모두 사용해도 괜찮으므로 if~elif가 아닌 if문을 두 개 사용해야 한다.