문제 이해하기
두 개의 문자열 S와 T가 주어졌을 때, S를 T로 변환하는 가장 짧은 연산 시퀀스를 찾아야 합니다. 여기서 허용되는 연산은 다음 두 가지입니다.
- 삭제(-): 문자열에서 문자 하나를 제거합니다.
- 삽입(+): 문자열에 새로운 문자 하나를 추가합니다.
예를 들어 입력이 S = "xxxy", T = "xxyy"라면 출력은 ["x", "x", "-x", "y", "+y"]가 됩니다. 이는 처음 두 개의 x를 그대로 유지하고, 세 번째 x를 삭제한 뒤, y를 유지하고 마지막에 새로운 y를 추가한다는 의미입니다.
접근 방법: 동적 계획법(DP)
이 문제는 메모이제이션을 활용한 동적 계획법으로 효율적으로 해결할 수 있습니다. 전체 알고리즘은 다음과 같습니다.
- 505 x 505 크기의 dp 테이블을 준비합니다.
- 최소 연산 횟수를 계산하는 함수 help()를 정의합니다. 이 함수는 인덱스 i, j와 문자열 S, T를 매개변수로 받습니다.
- i가 S의 길이와 같고 j가 T의 길이와 같으면 dp[i][j] = 0을 반환합니다.
- i가 S의 길이와 같으면(남은 문자는 모두 삽입) dp[i][j] = 1 + help(i, j+1, S, T)를 반환합니다.
- j가 T의 길이와 같으면(남은 문자는 모두 삭제) dp[i][j] = 1 + help(i+1, j, S, T)를 반환합니다.
- dp[i][j]가 이미 계산된 값(-1이 아님)이라면 해당 값을 그대로 반환합니다.
- dontDo := 1e5, del := 0, insert := 0으로 초기화합니다.
- S[i]와 T[j]가 같다면 dontDo := help(i+1, j+1, S, T)로 설정합니다.
- del := 1 + help(i+1, j, S, T), insert := 1 + help(i, j+1, S, T)를 계산합니다.
- minVal := min({dontDo, del, insert})를 구하고 dp[i][j] = minVal을 반환합니다.
- 실제 연산 경로를 복원하는 함수 getPath()를 정의합니다. 이 함수는 i, j, S, T, 현재 남은 연산 횟수 curr, 결과 배열 ret을 받습니다.
- curr이 0이고 i가 S의 길이, j가 T의 길이와 같으면 종료합니다.
- i < S의 길이, j < T의 길이이면서 S[i] == T[j]이고 dp[i+1][j+1] == curr이라면 문자 S[i]를 ret에 추가한 뒤 getPath(i+1, j+1, S, T, curr, ret)를 호출합니다.
- 그렇지 않고 dp[i+1][j] + 1 == curr이라면 "-" + S[i](삭제 연산)를 ret에 추가한 뒤 getPath(i+1, j, S, T, curr-1, ret)를 호출합니다.
- 위 조건에 해당하지 않으면 "+" + T[j](삽입 연산)를 ret에 추가한 뒤 getPath(i, j+1, S, T, curr-1, ret)를 호출합니다.
- 메인 로직에서는 다음 순서로 처리합니다.
- dp 배열을 -1로 초기화합니다.
- 결과를 담을 배열 ret을 선언합니다.
- x := help(0, 0, S, T)로 최소 연산 횟수를 구합니다.
- getPath(0, 0, S, T, x, ret)를 호출해 연산 시퀀스를 복원합니다.
- ret을 반환합니다.
C++ 구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v) {
cout << "[";
for (int i = 0; i < v.size(); i++) {
cout << v[i] << ", ";
}
cout << "]" << endl;
}
int dp[505][505];
class Solution {
public:
int help(int i, int j, string& S, string& T) {
if (i == S.size() && j == T.size())
return dp[i][j] = 0;
if (i == S.size())
return dp[i][j] = 1 + help(i, j + 1, S, T);
if (j == T.size())
return dp[i][j] = 1 + help(i + 1, j, S, T);
if (dp[i][j] != -1)
return dp[i][j];
int dontDo = 1e5;
int del = 0;
int insert = 0;
if (S[i] == T[j])
dontDo = help(i + 1, j + 1, S, T);
del = 1 + help(i + 1, j, S, T);
insert = 1 + help(i, j + 1, S, T);
int minVal = min({dontDo, del, insert});
return dp[i][j] = minVal;
}
void getPath(int i, int j, string& S, string& T, int curr, vector<string>& ret) {
if (curr == 0 && i == S.size() && j == T.size())
return;
if (i < S.size() && j < T.size() && S[i] == T[j] && dp[i + 1][j + 1] == curr) {
ret.push_back(string(1, S[i]));
getPath(i + 1, j + 1, S, T, curr, ret);
}else if (dp[i + 1][j] + 1 == curr) {
ret.push_back("-" + string(1, S[i]));
getPath(i + 1, j, S, T, curr - 1, ret);
}else {
ret.push_back("+" + string(1, T[j]));
getPath(i, j + 1, S, T, curr - 1, ret);
}
}
vector<string> solve(string S, string T) {
memset(dp, -1, sizeof dp);
vector<string> ret;
int x = help(0, 0, S, T);
getPath(0, 0, S, T, x, ret);
return ret;
}
};
vector<string> solve(string source, string target) {
return (new Solution())->solve(source, target);
}
main(){
string S = "xxxy", T = "xxyy";
print_vector(solve(S, T));
}입력
"xxxy", "xxyy"
출력
[x, x, -x, y, +y]