문제 소개
두 개의 문자열 s, t와 또 다른 문자열 r이 주어져 있다고 가정해 보겠습니다. 이 문제의 목표는 s와 t에 담긴 문자들을 원래 순서를 유지한 채 교차로 배치(인터리빙)했을 때 r을 만들어낼 수 있는지 확인하는 것입니다.
예를 들어 입력이 s = "xyz", t = "mno", r = "xymnoz"라면 결과는 True입니다. xymnoz는 xyz와 mno의 문자를 차례대로 섞어서 만들 수 있기 때문입니다.
해결 접근 방식
이 문제는 재귀 호출을 이용하면 자연스럽게 해결할 수 있습니다. 핵심 아이디어는 매 단계마다 r의 첫 글자가 s의 첫 글자와 같은지, 아니면 t의 첫 글자와 같은지를 검사하고, 일치하는 문자열에서 한 글자를 소모한 상태로 재귀 호출을 이어가는 것입니다.
구체적인 풀이 절차는 다음과 같습니다.
solve() 함수를 정의합니다. 이 함수는 s, t, r 세 개의 문자열을 인자로 받습니다.
s, t, r이 모두 빈 문자열이라면 True를 반환합니다.
r이 빈 문자열이라면 False를 반환합니다.
s가 빈 문자열이라면 t와 r이 동일할 때 True, 그렇지 않으면 False를 반환합니다.
t가 빈 문자열이라면 s와 r이 동일한지 여부를 반환합니다.
s[0]과 r[0]이 같다면, solve(s[1:], t, r[1:])의 결과가 참일 경우 True를 반환합니다.
t[0]과 r[0]이 같다면, solve(s, t[1:], r[1:])의 결과가 참일 경우 True를 반환합니다.
어떤 조건도 충족되지 않으면 False를 반환합니다.
구현 예제
아래 코드를 통해 실제 구현을 확인해 보겠습니다.
class Solution:
def solve(self, s, t, r):
if not s and not t and not r:
return True
if not r:
return False
if not s:
return t == r
if not t:
return s == r
if s[0] == r[0] and self.solve(s[1:], t, r[1:]):
return True
if t[0] == r[0] and self.solve(s, t[1:], r[1:]):
return True
return False
ob = Solution()
s = "xyz"
t = "mno"
r = "xymnoz"
print(ob.solve(s, t, r))
입력
"xyz", "mno", "xymnoz"
출력
True
동작 원리
첫 호출에서 r의 첫 글자 'x'가 s의 첫 글자 'x'와 일치하므로, s에서 'x'를 제거한 ("yz", "mno", "ymnoz") 상태로 재귀 호출이 진행됩니다. 이런 식으로 매번 일치하는 문자를 하나씩 소모하며 탐색이 이어지고, 마지막에는 세 문자열이 모두 소진되어 True가 반환됩니다.
반면 중간에 r의 첫 글자가 s와 t 어느 쪽의 첫 글자와도 일치하지 않거나, 남은 문자열이 서로 맞아떨어지지 않으면 해당 경로는 False로 종료됩니다. 이때 다른 선택지가 남아 있다면 백트래킹을 통해 나머지 경로도 계속 탐색합니다.
시간 복잡도
재귀 호출마다 최대 두 갈래로 분기할 수 있으므로, 위 구현의 최악의 시간 복잡도는 O(2^(n+m))입니다. 여기서 n과 m은 각각 s와 t의 길이입니다. 메모이제이션(memoization)을 적용해 이미 탐색한 (s, t) 조합을 캐싱하면 중복 연산을 제거하여 O(n×m)까지 성능을 개선할 수 있습니다.