[BOJ12919 - Python] A와 B 2

문제

---

12919번: A와 B 2

 

A와 B로만 이루어진 두 문자열 S와 T가 주어진다.

 

다음의 두 규칙으로 S를 T로 바꿀 수 있는지를 알아내는 것이 문제이다.

규칙 1. 문자열 뒤에 A 추가

규칙 2. 문자열 뒤에 B 추가 → 문자열 뒤집기

 

 

풀이

---

S를 T로 바꿀 수 있는지를 알아내는 것보다

T를 S로 되돌릴 수 있는지를 보는 것이 더 편하다.

 

우선, 여러 가지 시도를 해봤을 때

문자열의 맨 앞에 'A', 맨 뒤에 'B'가 오는 경우는 없다는 것을 발견할 수 있었다.

(1) A → A 추가 시 AA

(2) A → B 추가 시 AB

(3) B → A 추가 시 BA

(4) B → B 추가 시 BB

 

따라서 문자열 T를 S로 만들 수 있는지 판별해주는 재귀 함수를 다음과 같이 구현해주었다.

 

1. 두 문자열이 같은 경우 → return True

2. 'A__B'가 되는 경우 || 두 문자열의 길이가 같지만 다른 문자열인 경우 → return False

3. T의 맨 끝 문자가 'B' && 맨 끝 'B'를 제거하고 T를 뒤집어 재귀했을 때 True인 경우 → return True

4. T의 맨 앞 문자가 'A' && 맨 앞 'A'를 제거하여 재귀했을 때 True인 경우 → return True

 

코드

---

import sys

s = sys.stdin.readline().strip()
t = sys.stdin.readline().strip()


def change1(x):  # A 제거
    x = x[:-1]
    return x


def change2(x):  # B 제거 -> 문자열 뒤집기
    x = x[1:][::-1]
    return x


def check(s, t):
    # 두 문자열이 같을 경우
    if s == t:
        return True

    # 'A__B'가 되는 경우는 없음 / 두 문자열의 길이가 같은데 다른 문자열인 경우
    elif (t[0] == 'A' and t[-1] == 'B') or len(s) >= len(t):
        return False

    elif t[0] == 'B' and check(s, change2(t)):
        return True

    elif t[-1] == 'A' and check(s, change1(t)):
        return True

    else:
        return False


status = check(s, t)
if status:
    print(1)
else:
    print(0)