프로그래밍 면접 문제 6 : Combine Two Strings
프로그래밍 면접 문제 6 : Combine Two Strings
이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.
이전글 – 프로그래밍 면접 문제 5 : Linked List Remove Nodes
3개의 문자열 str1, str2, str3이 있습니다. str3은 str1과 str2 문자열의 각 문자를 결합해서 만드는데, str1, str2 각 문자열의 왼쪽부터 오른쪽 순서로 각 문자의 순서는 유지시키면서 문자를 결합합니다. 예를 들어, str1=”abc”이고 str2=”def”일때, str3=”dabecf”인 경우, str3은 str1과 str2의 각 문자 순서를 유지한 상태에서 문자를 결합시켰기 때문에 유효한 문자열입니다. 따라서, 주어지는 3개의 문자열에 대해서 str3 문자열이 str1과 str2를 유효하게 조합해서 만든 문자열인지 확인하는 함수를 작성하는 것이 이번 문제입니다.
이 문제를 해결하기 위해서 재귀(recursion)를 사용할 예정입니다. 하지만, 그 전에 먼저 확인해야할 것은 str1 문자열의 길이와 str2의 길이를 더한 길이가 str3 문자열의 길이와 같은지 확인합니다. 길이가 다른 경우, str3은 유효한 문자 조합이 아니기 때문에 그 즉시 false를 반환합니다. 재귀는 다음의 방식을 따릅니다. str1와 str3의 첫 번째 문자가 같은 경우, 첫 번째 문자를 제외한 나머지 문자에 대해서 반복해서 비교하고, str2 문자열은 그대로 둡니다. str2와 str3의 첫 번째 문자가 같은 경우, 위와 동일한 과정을 반복하고, str1은 그대로 둡니다. 지금 이 문제는 길이가 짧은 문자열에 대한 문제이기 때문에 재귀를 이용하는 것이 적합합니다. str1이나 str2의 첫 번째 문자이 str3의 첫 번째 문자와 모두 다른 경우, false를 반환합니다. str1, str2 둘 중 하나의 문자열이 빈 문자열인 경우 str1과 str2를 결합한 결과는 str3가 되어야 합니다. 다음은 이 풀이 방법의 파이썬 코드입니다:
def isShuffle(str1, str2, str3):
if len(str1) + len(str2) != len(str3):
return False
if not str1 or not str2 or not str3:
if str1 + str2 == str3:
return True
else:
return False
if str1[0] != str3[0] and str2[0] != str3[0]:
return False
if str1[0] == str3[0] and isShuffle(str1[1:], str2, str3[1:]):
return True
if str2[0] == str3[0] and isShuffle(str1, str2[1:], str3[1:]):
return True
return False
이 알고리즘은 재귀를 효율적으로 사용해서 동일한 문제를 더 작게 나눠서 이를 해결합니다. 하지만, 이 풀이 방법의 복잡도는 지수형태를 띕니다. 비교한 결과를 캐시(cache)에 저장해두지 않기 때문에, 동일한 입력 문자열에 대해서 반복해서 비교하는 경우가 발생할 수 있습니다. 이는 재귀 트리(recursion tree)를 그려보면 명확해 집니다. 또한 재귀 관계(recurrence relation)를 보고 검정할 수도 있습니다.
n은 str3 문자열의 문자 수를 나타냅니다. 이 관계에는 두 개의 용어가 존재하는데, 위에서 설명한 각 재귀에 대한 용어입니다. 재귀 관계는 피보나치 수와 유사하며, 지수함수 성격을 띕니다. 따라서, 사전 계산(precomputation)을 피하기 위해서는 동적 프로그래밍을(dynamic programming)을 수행하고, 이미 비교한 결과를 캐시(cache)에 저장해야 합니다. 두 입력 문자열이 유효한 문자열 조합을 생성하지 않는다는 것이 확인되면, 이 정보를 캐시에 저장합니다(유효한 문자열이 생성되면 True를 반환하기 때문에 캐시에 저장할 필요가 없습니다). 함수의 시작 부분에서 계산을 다시 시작하기 전에, 주어진 입력 문자열을 비교했는지 확인합니다. 캐시에 저장된 정보가 있다면(이미 비교했었다면), 계산을 다시 시도하지 않고 즉시 false를 반환합니다. 다음은 캐싱을 사용하는 코드입니다:
def isShuffle2(str1, str2, str3, cache=set()):
if (str1, str2) in cache:
return False
if len(str1) + len(str2) != len(str3):
return False
if not str1 or not str2 or not str3:
if str1 + str2 == str3:
return True
else:
return False
if str1[0] != str3[0] and str2[0] != str3[0]:
return False
if str1[0] == str3[0] and isShuffle2(str1[1:], str2, str3[1:], cache):
return True
if str2[0] == str3[0] and isShuffle2(str1, str2[1:], str3[1:], cache):
return True
cache.add((str1, str2))
return False
cache는 str1과 str2의 튜플(tuple)이 키(key)인 배열입니다. 유효한 문자열을 생성할 수 없는 경우를 미리 캐시에 저장하고, 계산을 다시 시도하기 전에 이를 확인합니다. 이 해결 방법의 복잡도는 O(NM)으로 N과 M은 각각 str1과 str2 문자열의 길이입니다. 따라서 지수함수의 복잡도를 동적 프로그래밍을 통해서 2차함수의 복잡도로 줄였습니다. 이는 최악의 경우에 대한 복잡도를 나타내지만, 평균적인 결과는 이보다 더 좋은 성능을 낼 것입니다.
이 문제는 효율적인 해결 방법을 얻기 위해서 재귀 및 동적 프로그래밍을 효과적으로 사용하는 방법을 보여주는 문제입니다.
