문제 설명
두 단어 w1과 w2가 주어졌을 때, 매 단계마다 두 문자열 중 하나에서 문자 하나를 삭제하여 두 단어를 완전히 같게 만들어야 합니다. 이때 필요한 최소 단계 수를 구하는 것이 목표입니다.
예를 들어 입력이 "sea"와 "eat"이라면 출력은 2가 됩니다. w1에서 's'를 삭제해 "ea"로 만들고, w2인 "eat"에서 't'를 삭제해 "ea"로 만들면 두 문자열이 같아지기 때문입니다.
해결 접근 방법
이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. dp[i][j]를 "s1의 앞 i개 문자와 s2의 앞 j개 문자를 같게 만드는 데 필요한 최소 삭제 횟수"로 정의합니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- n := s1의 길이, m := s2의 길이로 설정합니다.
- s1과 s2 앞에 공백 한 칸을 추가해 인덱스를 1부터 시작하도록 조정합니다.
- (n + 1) × (m + 1) 크기의 DP 테이블을 생성합니다.
- i를 1부터 m까지 순회하며
dp[0][i] := dp[0][i - 1] + 1로 초기화합니다. (s1이 빈 문자열이므로 s2의 문자를 모두 삭제해야 함) - i를 1부터 n까지 순회하며
dp[i][0] := dp[i - 1][0] + 1로 초기화합니다. (s2가 빈 문자열이므로 s1의 문자를 모두 삭제해야 함) - i를 1부터 n까지, j를 1부터 m까지 순회하며 다음 규칙으로 테이블을 채웁니다.
s1[i] == s2[j]라면:dp[i][j] := dp[i - 1][j - 1]— 현재 문자가 서로 같으므로 추가 삭제가 필요 없습니다.- 그렇지 않다면:
dp[i][j] := min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)— 어느 한쪽의 문자를 삭제하는 두 경우 중 최솟값을 선택합니다.
- 최종적으로
dp[n][m]을 반환합니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minDistance(string s1, string s2) {
int n = s1.size();
int m = s2.size();
s1 = " " + s1;
s2 = " " + s2;
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for(int i = 1; i <= m; i++){
dp[0][i] = dp[0][i - 1] + 1;
}
for(int i = 1; i <= n; i++){
dp[i][0] = dp[i - 1][0] + 1;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(s1[i] == s2[j]){
dp[i][j] = dp[i - 1][j - 1];
}
else{
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
}
}
}
return dp[n][m];
}
};
main(){
Solution ob;
cout << (ob.minDistance("sea", "eat"));
}입력
"sea"
"eat"
출력
2
복잡도 분석 및 참고 사항
시간 복잡도와 공간 복잡도는 모두 O(n × m)입니다. 여기서 n과 m은 각각 두 문자열의 길이입니다.
참고로 이 문제는 최장 공통 부분 수열(LCS, Longest Common Subsequence)과 밀접한 관련이 있습니다. 두 문자열 길이의 합에서 공통 부분 수열 길이의 2배를 빼면 곧바로 답을 얻을 수 있습니다. 즉, 답 = (n + m) − 2 × LCS(s1, s2)이며, 위 DP 풀이는 이 아이디어를 직접 구현한 것과 본질적으로 같습니다.