문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.
LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.
풀이
두 문자열의 공통 부분 수열 길이는 dp[i][j]를 첫 번째 문자열의 앞 i글자와 두 번째 문자열의 앞 j글자까지 봤을 때의 최장 공통 부분 수열 길이로 두면 구할 수 있다.
문자가 같으면 대각선 값에 1을 더하고, 다르면 위와 왼쪽 중 큰 값을 가져오는 전형적인 점화식을 사용한다. LCS 2처럼 실제 수열까지 필요하면, DP를 채운 뒤 뒤에서부터 역추적해 어떤 문자가 선택됐는지 복원하면 된다.
길이 계산은 DP, 실제 문자열 복원은 역추적으로 나뉜다.
코드
import java.io.*;
public class Main {
static int[][] LCS;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s1 = br.readLine();
String s2 = br.readLine();
String ans = solve(s1, s2);
System.out.println(ans);
}
static String solve(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
LCS = new int[len1 + 1][len2 + 1];
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1))
LCS[i][j] = LCS[i - 1][j - 1] + 1;
else
LCS[i][j] = Math.max(LCS[i - 1][j], LCS[i][j - 1]);
}
}
StringBuilder sb = new StringBuilder();
int i = len1;
int j = len2;
while (i > 0 && j > 0) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
sb.append(s1.charAt(i - 1));
i--;
j--;
} else if (LCS[i - 1][j] > LCS[i][j - 1]) {
i--;
} else {
j--;
}
}
return String.valueOf(LCS[len1][len2]) + '\n' + sb.reverse().toString();
}
}복잡도
- 시간 복잡도:
- 공간 복잡도:
마무리
LCS는 결국 두 접두사 사이의 최적해를 쌓아 가는 DP다. 수열까지 필요하면 마지막에 역추적만 한 번 더 해 주면 된다.
