사용 이론 - Dynamic Programming, LCS
문제에서 부분 문자열은 연속되지 않아도 되며, 순서가 지켜지기만 하면 되기 때문에, 최장 공통 부분 수열 개념으로 풀어야 했다.
최장 공통 부분 수열(Longest Common Subsequence, LCS)은 두 개의 문자열에서 공통으로 존재하는 부분 수열 중 가장 긴 것을 찾는 알고리즘 방식이다.
풀이 방식
두 문자열의 길이와 같은 길이를 갖는 dp용 이차원 배열을 만들었다.
dp 각 칸에 저장된 값은 해당 위치에서의 LCS 문자열의 길이를 나타낸다.
LCS 길이 구하기
그리고 두 문자열을 한글자씩 비교한다. 이때,
1. 두 문자가 다르면 LCS[i - 1][j]와 LCS[i][j - 1] 중에 큰 값을 표시하고,
2. 두 문자가 같다면 LCS[i - 1][j - 1] 값을 찾아 1을 더해준다.
이 과정을 점화식으로 나타낸다.
int m = wordA.length(), n = wordB.length();
int[][] dp = new int[m + 1][n + 1];
// LCS를 구하기 위한 다이나믹 프로그래밍
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (wordA.charAt(i - 1) == wordB.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}여기서 문자가 다를 때와 같을 때 상황에 대해 좀 더 알아보자.
다를 때 : Math.max(LCS[i - 1][j], LCS[i][j - 1])
dp를 사용하기 때문에 현재의 문자를 비교하는 과정 이전의 최대 공통 부분수열은 계속 저장된다.
그래서 현재 비교 시 문자가 다르면 현재의 비교는 이전의 비교를 통해 산출됐던 LCS, 즉 LCS[i - 1][j]와 LCS[i][j - 1]가 된다.
여기서 이전의 비교는, 각각의 지금의 문자열로부터 각각의 문자열 기준 하나씩 이전의 문자열과 비교했던 값과 같다.
같을 때 : LCS[i - 1][j - 1] + 1
위의 다른 경우에서의 맥락으로 봤을 때, 지금 비교하는 문자열이 같다면 지금의 문자열을 추가하기 위해 1을 더한다!
LCS 문자열 구하기
이제 앞서 구한 LCS 갯수 정보가 담긴 dp 배열을 활용해 문자열을 찾아야 한다.
// LCS를 역추적하여 구하기
StringBuilder password = new StringBuilder();
int i = wordA.length(), j = wordB.length();
while (i > 0 && j > 0) {
if (wordA.charAt(i - 1) == wordB.charAt(j - 1)) {
password.append(wordA.charAt(i - 1));
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}역시 두 문자열을 하나씩 순회하면서 비교하는 방식을 선택했고, 같은 문자열은 StringBuilder에 넣어주는 방식으로 구현했다.
이때 비교하는 문자열이 다를 경우
만약 dp[i - 1][j] > dp[i][j - 1]이면, 이전 행에서 온 것이 더 큰 값이므로 i를 1 감소시켜서 위쪽으로 이동하고,
dp[i - 1][j] <= dp[i][j - 1]이면, 이전 열에서 온 것이 더 크거나 같은 값이므로 j를 1 감소시켜서 왼쪽으로 이동한다.
최종 코드
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String wordA = br.readLine();
String wordB = br.readLine();
br.close();
int m = wordA.length(), n = wordB.length();
int[][] dp = new int[m + 1][n + 1];
// LCS를 구하기 위한 다이나믹 프로그래밍
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (wordA.charAt(i - 1) == wordB.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// LCS를 역추적하여 구하기
StringBuilder password = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if (wordA.charAt(i - 1) == wordB.charAt(j - 1)) {
password.append(wordA.charAt(i - 1));
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
System.out.println(password.reverse());
}
}참고
