LeetCode의 Delete Operation for Two Strings 문제를 함께 풀어보도록 하겠습니다.
문제
두 개 문자열이 주어졌을 때, 두 개의 문자열을 똑같게 만들기 위해서 삭제해야하는 최소한의 글자 수를 구하라.
예제
Input: word1 = "sea", word2 = "eat"
Output: 2"sea"에서 "s"를 삭제하고, "eat"에서 "t"를 삭제하면 동일하게 "ea"가 남는다.
따라서, "s", "t" 이렇게 총 2개의 글자를 삭제해야한다.
풀이 1
주어진 예제를 통해서 이 문제를 어떻게 풀 수 있을지 한번 생각해보겠습니다.
"sea"와 "eat"의 첫 글자를 비교해보면 다르기 때문에 적어도 둘 중에 하나는 삭제를 해야한다는 것을 알 수 있습니다.
여기서 우리는 2가지 경우의 수가 생기는데요.
- 만약에
"sea"의 첫 번째 글자인"s"를 삭제한다면,"ea"와"eat"를 똑같게 만들기 위해서 삭제해야하는 최소한의 글자 수가 필요할 것입니다. - 만약에
"eat"의 첫 번째 글자인"e"를 삭제한다면,"sat"와"at"를 똑같게 만들기 위해서 삭제해야하는 최소한의 글자 수가 필요할 것입니다.
우리는 삭제해야하는 최소한의 글자의 수가 필요하기 때문에 이 둘 중에 더 작은 값을 선택한 후, 어느 경우를 선택하든 1개의 글자는 삭제하는 것이기 때문에 1을 더해야 할 것입니다.
F()를 두 개의 문자열을 똑같게 만들기 위해서 삭제해야하는 최소한의 글자 수를 구하는 함수라고 한다면 첫글자가 다른 "sea"와 "eat"의 경우 다음과 같이 계산이 됩니다.
F("sea", "eat") = 1 + min(F("ea", "eat"), F("sea", "at"))이를 통해서 이 문제는 재귀 알고리즘으로 풀 수 있다는 것을 알 수 있습니다. 입력 값이 큰 하나의 문제를 입력 값이 작은 하위 문제 두 개의 문제로 나눠서 접근하는 전형적인 재귀 알고리즘의 모습입니다.
위의 첫 번째 경우의 수에서 "ea"와 "eat"를 똑같게 만들기 위해서 삭제해야하는 최소한의 글자 수가 필요하다고 있는데요.
이 두 문자열을 똑같에 만들기 위해서 삭제해야하는 최소한의 글자수는 어떻게 구할까요?
이번에는 첫 글자가 동일하기 때문에 아무 것도 삭제할 필요가 없습니다.
따라서, "ea"와 "eat"와 같이 두 문자열의 첫 글자가 같을 때는 다음과 같이 해당 문자를 그냥 무시하면 됩니다.
F("ea", "eat") = F("a", "at")"a"와 "at"도 첫 글자가 같으므로 동일한 경우가 해당하겠네요.
F("a", "at") = F("", "t")""와 "t"를 꼬같게 만들기 위해서는 "t"만 삭제하면 됩니다.
이렇게 둘 중에 하나가 빈 문자열인 경우 다른 문자열의 모든 문자를 삭제해야합니다.
이 경우를 재귀 함수의 기저 사례(base case)로 사용할 수 있겠습니다.
"sea"와 "eat"가 주어졌을 때, 재귀 함수가 어떻게 연쇄적으로 호출되는지를 아래와 같이 시각해볼 수 있습니다.
F("sea", "eat") => 1 + min(1, 2) => 2
F("ea", "eat") => 1
F("a", "at") => 1
F("", "t") => 1
F("sea", "at") => 1 + min(2, 4) = 3
F("ea", "at") => 1 + min(1, 3) => 2
F("a", "at") => 1
F("", "t") => 1
F("ea", "t") => 1 + min(2, 2) => 3
F("a", "t") => 1 + min(1, 1) = 2
F("", "t") => 1
F("a", "") => 1
F("ea", "") => 2
F("sea", "t") => 1 + min(3, 3) = 4
F("ea", "t") => 1 + min(2, 2) = 3
F("a", "t") => 1 + min(1, 1) = 2
F("", "t") => 1
F("a", "") => 1
F("ea", "") => 2
F("sea", "") => 3이 재귀 알고리즘을 코드로 구현해보겠습니다.
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
def dfs(i, j):
if i == len(word1):
return len(word2) - j
if j == len(word2):
return len(word1) - i
if word1[i] == word2[j]:
return dfs(i + 1, j + 1)
return 1 + min(dfs(i + 1, j), dfs(i, j + 1))
return dfs(0, 0)첫 번째 문자열의 길이를 m, 두 번째 문자열의 길이를 n이라고 한다면, 이 풀이의 시간 복잡도는 O(2^(mn)) 입니다.
왜냐하면 재귀 호출을 할 때 마다 최악의 경우, 즉 두 문자열 간에 같은 문자가 하나도 없을 경우에는 2번씩 연쇄 호출이 일어나기 때문입니다.
이 재귀 호출 스택은 최대 두 문자열로 부터 만들 수 있는 모든 문자의 쌍만큼 깊어질 수 있기 때문에 공간 복잡도는 O(mn) 입니다.
참고로 이 풀이의 시간 복잡도는 메모이제이션(memoization) 기법을 이용하여 중복 계산을 제거하면 O(mn)로 개선할 수 있습니다.
풀이 2
위 재귀 알고리즘은 Top-down 방향으로 문제에 접근하고 있는데요. 이번에는 반대로 Bottom-up 방향으로 문제에 접근해보면 어떨까요?
즉, 빈 문자열이 주어진 경우부터 시작해서 전체 문제열이 주어진 경우까지 거슬러 올라가는 것입니다.
먼저 아주 간단한 경우에 대해서 생각해보면 좋을 것 같아요.
예를 들어, "a"와 "ab"를 똑같게 만들기 위해서는 두 번째 문자열에서 "b" 하나만 삭제하면 되죠?
두 개의 빈 문자열이 주어졌다면 지울 글자가 자체가 없으므로 삭제 가능한 글자의 수는 0일 것입니다.
"" vs "" => 0첫 번째 문자열은 빈 문자열로 두고 두 번째 문자열에서 첫 번째 문자를 고려하면 삭제해야 할 글자의 수는 1이 되지요.
"" vs "a" => 1마찬가지로 두 번째 문자열에서 두 번째 문자까지 고려하면 삭제해야 할 글자의 수는 2가 됩니다.
"" vs "ab" => 2이번에는 첫 번째 문자열에 첫 번째 문자를 추가하고, 두 번째 문자열에 빈 문자열로 놓아보면 삭제해야 할 글자의 수는 1이 됩니다.
"a" vs "" => 1첫 번째 문자열은 그대로 두고 두 번째 문자열에서 첫 번째 문자까지 고려하면 삭제해야 할 글자의 수는 0이 됩니다.
"a" vs "a" => 0왜 0이 될까요? 동일해서 지울 필요가 없는 "a"를 제외하고 생각하면 위에서 이미 다뤘던 빈 문자열 두 개가 주어진 경우와 동일하게 때문입니다.
"" vs "" => 0마지막으로 두 번째 문자열에서 두 번째 문자까지 고려하면 삭제해야 할 글자의 수는 1이 됩니다.
"a" vs "ab" => 1왜 1이 될까요? 두 문자열의 마지막 글자인 "a"와 "b"는 다르기 때문에 적어도 둘중에 하나는 삭제해야 합니다.
첫 번째 문자열에서 "a"를 삭제해보면 다음 경우가 되는데 위에서 이미 다루었고요.
"" vs "ab" => 2두 번째 문자열에서 "b"를 삭제해보면 다음 경우가 되는데 역시 위에서 이미 다루었습니다.
"a" vs "a" => 0삭제해야하는 최소한의 글자의 수가 필요하기 때문에 이 둘 중에 더 작은 값인 0을 선택해야겠죠?
즉, 두 번째 문자열에서 "b"를 삭제하는 것이 유리하고 그래서 결과적으로 하나의 문자만 삭제하면 되는 것입니다.
이렇게 이전 단계에서 계산한 결과를 현재 단계에서 재사용이 가능하다면 다이나믹 프로그래밍(Dynamic Programing)을 적용할 수 있습니다. 지금까지 거쳐온 과정에서 규칙을 도출해보겠습니다.
dp[i][j]를word1에서 처음i개의 문자,word2에서 처음j개의 문자를 똑같에 만들기 위해서 삭제해야하는 최소한의 글자 수라고 가정하면word1[i - 1]과word2[j - 1]이 같은 문자이면,dp[i][j]는dp[i - 1][j - 1]이 된다.word1[i - 1]과word2[j - 1]이 다른 문자이면,dp[i][j]는1 + min(dp[i - 1][j], dp[i][j - 1])이 된다.
"a"와 "ab"를 똑같게 만들기 위해서 삭제해야하는 최소한의 글자의 수를 2차원 배열에 저장해보면 다음과 같습니다.
_ a b
_ [0, 1, 2]
a [1, 0, 1]마찬가지 방법으로 문제에서 주어진 예제인 "sea"와 "see"를 똑같게 만들기 위해서 삭제해야하는 최소한의 글자의 수를 다음과 같이 저장할 수 있습니다.
_ e a t
_ [0, 1, 2, 3]
s [1, 2, 3, 4]
e [2, 1, 2, 3]
a [3, 2, 1, 2]이 다이나믹 프로그래밍 알고리즘을 코드로 구현해볼까요?
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]
for i in range(len(word2) + 1):
dp[0][i] = i
for j in range(len(word1) + 1):
dp[j][0] = j
for i in range(1, len(word1) + 1):
for j in range(1, len(word2) + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])
return dp[-1][-1]이중 루프를 사용하고 있으므로 이 풀이의 시간 복잡도는 O(mn)이 되며, 공간 복잡도도 2차원 배열을 사용하므로 O(mn) 입니다.
풀이 3
위 동적 계획법 알고리즘은 조금만 더 머리를 굴려보면 2차원 배열 대신에 1차원 배열만을 사용하도록 공간 최적화가 가능합니다.
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
prev = [0 for _ in range(len(word2) + 1)]
for i in range(len(word1) + 1):
curr = [0 for _ in range(len(word2) + 1)]
for j in range(len(word2) + 1):
if i == 0:
curr[j] = j
elif j == 0:
curr[j] = i
elif word1[i - 1] == word2[j - 1]:
curr[j] = prev[j - 1]
else:
curr[j] = 1 + min(prev[j], curr[j - 1])
prev = curr
return prev[len(word2)]이 풀이의 시간 복잡도는 O(mn), 공간 복잡도는 O(n) 입니다.