Interleaving String
문자열 세 개 s1, s2, s3가 주어진다. 이때, s1과 s2의 글자를
서로 사이에 끼워서(interleaving) s3를 만들 수 있는지 없는지
판별하자.
두 문자열 s와 t를 서로 사이에 끼우는 연산은 다음 조건을
만족하는 비지 않은 부분 문자열로 나눠지는 것을 의미한다:
s = s1 + s2 + ... + snt = t1 + t2 + ... + tm| n - m | <= 1- 서로 사이에 끼운 문자열은
s1 + t1 + s2 + t2 + ...이거나t1 + s1 + t2 + s2 + ...이다.
참고로 a + b는 문자열 a와 b를 잇는 것이다.
s1과 s2의 길이는 0 ~ 100 사이이고 s3는 0 ~ 200 사이이다. 모두
알파벳 소문자만 담고 있다.
예를 들어 s1 = aabcc, s2 = dbbca, s3 = aadbbcbcac라고
하자. 이때, s1을 aa, bc, c 로, s2를 dbbc, a로 나눈 다음
s1부터 번갈아 끼우면 aa + dbbc + bc + a + c = s3가 되므로 정답은
참이다.
동적 프로그래밍은 완전 탐색부터
일단 단순히 각 문자열에 있는 글자 개수를 세서 비교하는 접근은
안된다. 부분 문자열의 순서가 중요하고, 또 s1과 s2가 서로
번갈아 나와야 하기 때문이다.
가장 먼저 완전 탐색 알고리즘부터 생각해보자. 일단 기저 조건으로, 각
문자열의 글자 수가 아니라 문자열의 길이가 맞지 않으면 불가능하다. 즉
|s1| + |s2| != |s3|인 경우는 아예 인터리빙 자체가 불가능하다.
그럼 이제 문자열 길이가 맞춰진 경우를 생각해보자. s1, s2, s3에
대해서 각각 지금 어느 부분의 글자를 탐색하고 있는지를 알기 위해서 세
인덱스 i1, i2, i3를 유지하자. 먼저 s1이 먼저 나오는 경우부터
생각해보자. s1[i1]의 글자가 s3[i3]와 같은 경우에 다음 둘 중
하나를 진행할 수 있다:
- 만약 또
s1[i1 + 1]이s3[i1 + 1]과 같다면, 계속 같을 때 까지 이어나간다. s2[i2]가s3[i + 1]과 같다면, 이번에는s2를 선택해서 이어나간다.
s2가 먼저 나오는 경우도 위와 비슷하다. 즉, 만약 i1, i2 모두
0부터 시작하여 s1과 s2를 번갈아 재귀적으로 확인한다면, 모든
경우의 수를 확인할 수 있다.
이렇게 계속 이어나간다면, 언제 탐색이 종료될까? s1이든 s2든 한쪽
문자열의 끝에 도달한 경우일 것이다. 예를 들어 i1이 s1의 끝에
도달했다면, 남은 것은 다음을 확인하는 것이다: s2에 대해서 i2
이후의 부분문자열이, s3에 대해서 i3 이후의 부분문자열과
같은지. 즉, i1은 더 이상 매칭이 불가능하니, 남은 모든 기운(?)을
써서 s2의 남은 부분문자열과 s3의 남은 부분문자열이 같기를 바라는
것이다.
말로 설명하니 뭔가 꼬이는 것 같은데, 코드로 나타내면 아래와 같다.
def isInterleave(s1, s2, s3):
if len(s1) + len(s2) != len(s3):
return False
def check(i1, i2, i3):
if i1 == len(s1):
return s2[i2:] == s3[i3:]
if i2 == len(s2):
return s1[i1:] == s3[i3:]
return (s1[i1] == s3[i3] and check(i1 + 1, i2, i3 + 1)) \
or (s2[i2] == s3[i3] and check(i1, i2 + 1, i3 + 1))
return check(0, 0, 0)
check 함수가 앞에서 설명한 재귀적인 확인을 한다. 기저 조건은 i1
또는 i2가 끝에 도달했을 때 이다. 앞에서 미리 글자 수가 다른 경우를
걸러내기 때문에, i1 또는 i2가 끝에 도달했을 때 s2[i2:] 또는
s1[i1:]은 남은 s3[i3:] 부분문자열과 항상 길이가 같음이 보장된다.
교묘한 부분은 재귀를 타고들어가는 부분이다. s1[i1] == s3[i3], 즉
지금 s1의 부분문자열의 일부가 먼저 나올 수 있는 상황이라면, i1과
i3를 동시에 하나씩 진행한다. s2의 경우도 비슷하다. 이렇게하면 (1)
s1와 s2가 번갈아 올 수 있는 모든 경우를 확인하면서 (2) 둘 중
하나가 끝에 도달했을 때 나머지를 전부 확인하는, 문제의 조건을
만족하게 된다.
당연하지만, 이렇게하면 복잡도가 지수적이라서 터진다. s1의 길이를
n, s2의 길이를 m이라고 했을 때, s3의 길이는 n + m이 되고
모든 s3의 각 글자에 대해서 s1 또는 s2 두 가지 경우가
가능하므로, 시간 복잡도는 \(O(2 ^ {n + m})\)이 된다.
메모아이제이션
그럼 복잡도를 낮출 수 있는 방법을 찾아보자. 재귀가 일어날 때, i3는
항상 증가하지만 i1와 i2는 둘 중 하나만 증가한다. 따라서 잘
생각해보면, i3가 1 증가하면, i1이 1 증가하기 전과 i2가 1
증가하기 전 모두를 살펴보게 된다. 그림으로 그리면 다음과 같다.
i3 | 0 -----------> 1 ----------> 2 ---------------> 3
(i1, i2) | (0, 0) (0, 1) (0, 2) (0, 3), (1, 2)
| (1, 1) (1, 2), (2, 1)
| (1, 0) (2, 0) (2, 1), (3, 0)
| (1, 1) (1, 2), (2, 1)
즉, i3 = 3 일 때, (i1, i2)는 꽤 많이 중복된다: (1, 2)가 세번,
(2, 1)도 세번. 따라서, s3(i3)를 기준으로 생각해보면, s1과
s2의 일부를 반드시 중복해서 보게 된다. 입력 문자열이 변하지 않기
때문에 이 반복되는 부분은 i3의 값에 상관없이 변하지 않는다. 따라서
최적 부분구조(optimal substructure)를 가지고 있다고 판단할 수
있고, 이를 캐싱해서 속도를 높일 수 있다.
i1, i2 페어에 대해서 기존에 결과를 빠르게 돌려주면 되므로, 다음과
같이 메모아이제이션을 하면 된다.
def isInterleave(s1, s2, s3):
memo = {}
def check(i1, i2, i3):
if i1 == len(s1):
return s2[i2:] == s3[i3:]
if i2 == len(s2):
return s1[i1:] == s3[i3:]
if (i1, i2) in memo:
return memo[(i1, i2)]
res = (s1[i1] == s3[i3] and check(i1+1, i2, i3+1)) \
or (s2[i2] == s3[i3] and check(i1, i2+1, i3+1))
memo[(i1, i2)] = res
return res
return check(0, 0, 0)
이를 통해 시간과 공간 복잡도 모두 O(nm)의 솔루션을 얻을 수 있다.