문제가 궁금하시다면 아래의 링크를 눌러주세요!
문제 보러가기
접근 과정
문자열 S를 문자열 T와 같게 하기 위해서, 문자열의 맨 뒤에 A를 추가하거나, 맨 뒤에 B를 추가하고 문자열을 뒤집는 행위를 문자열 T의 길이 - 문자열 S의 길이만큼 반복하게 된다. (같게 만든다는 것은, 두 문자열의 길이가 동일하다는 것을 의미하기 때문)
문제 내 테스트 케이스인 A 와 BABA의 경우를 살펴보면...
이렇게 매 순간마다 문자열의 맨 뒤에 A를 붙이거나 B를 붙이고 뒤집는다는 선택의 과정들을 재귀를 통해 구현하고, 문자열 S가 T와 동일한 길이가 되었을 때, 두 문자열이 동일한지 비교할 수 있다.
하지만 이 방법의 문제는 문자열 T의 길이 - 문자열 S의 길이인 N을 기준으로 O(2^N)의 시간 복잡도가 발생하게 된다는 것이다.
문제의 조건을 기준으로, 문자열 S의 최소값은 1, 문자열 T의 최대값은 50이기 때문에 최악의 상황 기준으로는 문자열 S에서 출발해 문자열 T와 동일한 길이를 찾아가는 과정은 최대 O(2^49)에 가까운 연산을 요구한다!
시간 제한 내에 S -> T 가 불가능하다면, 어떻게 해야 할까? 생각하다 반대로 문자열 T에서 문자를 하나씩 제거해가면서 문자열 S와 같게 만들 수 있을지 생각하게 되었다.
문자열 T에서 문자열 S로 만드는 과정은, 크게 2가지로 나눌 수 있다.
1. 문자열 가장 뒤의 A를 하나 제거한다
2. (문자열 가장 처음 요소가 B인 경우) 문자열 가장 앞의 B를 제거하고, 뒤집는다
이 조건을 기준으로 문자열 T에서 접근해보게 되면...
조건을 충족하지 않는 경우 이후의 로직을 수행하지 않을 것이기 때문에, 문자열 S에서 T로 향하는 과정에 비해 더 적은 연산을 수행하게 된다!
하지만 이렇게만 진행하게 되면, 한 가지 문제가 발생한다.
문자열 T로부터 시작해 문자열 S와 동일하게 만들기 위해 연산을 수행하는 임의의 문자열 X가 B로 시작해서 A로 끝나는 경우를 별도로 고려해야 한다는 것이다!
이 경우 문자열 가장 뒤의 A를 제거하거나, 문자열 가장 앞의 B를 제거한 뒤 뒤집는 2가지의 연산이 전부 가능하기 때문에 단순히 문자열의 맨 앞이 B이면, 맨 앞의 B를 제거하고 뒤집는 방향으로만 조건을 설정할 경우 틀리는 케이스가 발생하기 때문이다.
짧게 줄여 말하자면 문자열의 첫 요소가 A인지 아닌지로 if - else 구문을 사용하거나, A인지 B인지 if - else if구문으로 접근하면 안된다는 말이다! 전부 별개의 if 구문으로 접근해야 한다.
정리하면...
1. 연산 횟수를 줄이기 위해, S -> T가 아닌 T -> S를 고려해야 한다.
2. 고려할 대상은 아래의 3가지!
2.1. 문자열의 맨 앞이 A이고 끝이 A인 경우 -> 가장 뒤의 A를 제거한다.
2.2. 문자열의 맨 앞이 B이고 끝이 B인 경우 -> 가장 앞의 B를 제거하고, 문자열을 뒤집는다.
2.3. 문자열의 맨 앞이 B이고 끝이 A인 경우 -> 위의 2가지 연산을 전부 수행한다!
3. 이 과정을 총 문자열 T의 길이 - 문자열 S의 길이인 N회 만큼 반복해 문자열 S와 동일한 길이일 때, S와 동일한 문자열인지 확인한 뒤 값을 반환한다!
풀이
import sys
sys.setrecursionlimit(10000)
def calc(t):
global flag
if t == S:
print(1)
flag = True
return
# 문자열 t가 문자열 S와 동일한 길이일 때까지만 연산해야 두 문자열이 동일한지 비교가 가능하기 때문에, 길이가 더 짧아지게 되면 더 이상 진행할 필요가 없다.
# 또, 이미 문자열 t와 S가 동일한 경우를 찾게 되면 그 이후는 진행할 필요가 없기에 flag가 True가 되면 바로 빠져나오게 진행한다.
if len(S) > len(t) or flag: return
if t[0] == 'A' and t[-1] == 'A':
temp = t[:-1]
calc(temp)
elif t[0] == 'B' and t[-1] == 'B':
temp = t[::-1][:-1]
calc(temp)
elif t[0] == 'B' and t[-1] == 'A':
# B로 시작해서 A로 끝나는 경우, 2가지의 연산이 전부 가능하다.
temp1 = t[:-1]
calc(temp1)
temp2 = t[::-1][:-1]
calc(temp2)
input = sys.stdin.readline
S = input().rstrip()
T = input().rstrip()
flag = False
calc(T)
if not flag:
print(0)읽어주셔서 감사합니다!
