문제 개요
두 문자열 str1과 str2가 주어졌을 때, 두 문자열을 모두 부분 수열(subsequence)로 포함하는 가장 짧은 문자열을 찾는 것이 이번 글의 목표입니다. 정답이 여러 개 존재할 수 있으므로 그중 하나만 반환하면 됩니다.
여기서 문자열 S가 문자열 T의 부분 수열이라는 것은, T에서 임의의 위치에 있는 일부 문자(0개일 수도 있음)를 삭제했을 때 S가 된다는 의미입니다.
예를 들어 입력이 "acab"과 "bac"라면 출력은 "bacab"이 됩니다. 두 문자열 모두 "bacab"의 부분 수열이기 때문입니다.
해결 접근 방법
이 문제는 최장 공통 부분 수열(LCS, Longest Common Subsequence)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 먼저 두 문자열의 LCS를 구한 뒤, LCS에 포함되지 않는 나머지 문자들을 적절한 순서로 삽입하여 초수열(supersequence)을 완성하는 것입니다.
1단계: getLCS()로 LCS 구하기
getLCS() 함수는 다음 순서로 동작합니다.
- 빈 문자열 ret을 준비하고, n := s1의 길이, m := s2의 길이로 설정합니다.
- (n + 1) × (m + 1) 크기의 2차원 배열 dp를 선언합니다.
- i := n, j := m으로 초기화하고, s1과 s2 앞에 빈 문자를 하나 붙여 인덱스를 1부터 사용할 수 있도록 맞춥니다.
- 이중 반복문으로 dp 테이블을 채웁니다.
- s1[i]와 s2[j]가 같으면 → dp[i][j] = 1 + dp[i-1][j-1]
- 다르면 → dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- dp 테이블을 역추적합니다(i와 j가 0이 아닌 동안 반복).
- dp[i][j] == dp[i-1][j]이면 i를 1 감소시키고 다음 반복으로 건너뜁니다.
- dp[i][j] == dp[i][j-1]이면 j를 1 감소시키고 다음 반복으로 건너뜁니다.
- 그 외에는 ret에 s1[i]를 추가하고 i, j를 각각 1씩 감소시킵니다.
- 역추적 과정에서 문자가 거꾸로 쌓이므로 마지막에 ret을 뒤집어 반환합니다.
2단계: 초수열 조합하기
메인 로직에서는 구한 LCS(s3)를 기준으로 두 문자열을 병합합니다.
- s3 := getLCS(str1, str2)를 호출하고, ret := 빈 문자열, i := 0, j := 0, k := 0으로 초기화합니다.
- k가 s3의 길이보다 작은 동안 반복합니다.
- i < str1의 길이이면서 str1[i] != s3[k]이면 → ret에 str1[i]를 추가하고 i를 증가시킨 뒤 다음 반복으로 넘어갑니다.
- j < str2의 길이이면서 str2[j] != s3[k]이면 → ret에 str2[j]를 추가하고 j를 증가시킨 뒤 다음 반복으로 넘어갑니다.
- 그 외에는 → ret에 s3[k]를 추가하고 i, j, k를 모두 1씩 증가시킵니다.
- 반복이 끝난 후 str1에 남아 있는 문자를 모두 ret에 추가합니다.
- str2에 남아 있는 문자도 모두 ret에 추가합니다.
- ret을 반환합니다.
C++ 구현 예제
아래 코드를 통해 전체 흐름을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string shortestCommonSupersequence(string str1, string str2){
string s3 = getLCS(str1, str2);
string ret = "";
int i = 0;
int j = 0;
int k = 0;
while (k < s3.size()) {
if (i < str1.size() && str1[i] != s3[k]) {
ret += str1[i];
i++;
continue;
}
if (j < str2.size() && str2[j] != s3[k]) {
ret += str2[j];
j++;
continue;
}
ret += s3[k];
k++;
i++;
j++;
}
while (i < str1.size()) {
ret += str1[i];
i++;
}
while (j < str2.size()) {
ret += str2[j];
j++;
}
return ret;
}
string getLCS(string s1, string s2){
string ret = "";
int n = s1.size();
int m = s2.size();
vector<vector<int> > dp(n + 1, vector<int>(m + 1));
int i = n;
int j = m;
s1 = " " + s1;
s2 = " " + s2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1[i] == s2[j]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
while (i && j) {
if (dp[i][j] == dp[i - 1][j]) {
i--;
continue;
}
if (dp[i][j] == dp[i][j - 1]) {
j--;
continue;
}
ret += s1[i];
i--;
j--;
}
reverse(ret.begin(), ret.end());
return ret;
}
};
main(){
Solution ob;
cout << (ob.shortestCommonSupersequence("acab", "bac"));
}
입력
"acab", "bac"
출력
bacab
복잡도 및 정리
이 알고리즘의 시간 복잡도는 dp 테이블을 채우고 역추적하는 과정에서 O(n × m)이며, 공간 복잡도 역시 dp 테이블 저장을 위해 O(n × m)입니다(n, m은 각 문자열의 길이).
정리하면, 최단 공통 초수열 문제는 LCS를 먼저 구한 뒤 두 문자열을 LCS를 기준으로 병합하는 방식으로 깔끔하게 해결할 수 있습니다. 이 접근법은 문자열 병합, DNA 서열 정렬 등 다양한 실무 문제에도 응용될 수 있으므로 동적 계획법 학습의 좋은 예제가 됩니다.