Link | 백준 9252번 문제 : LCS 2
전형적인 LCS(Subsequence) 문제이다.
다만, LCS 1 문제와 차이점은 최장 길이 뿐만이 아니라 최장 공통 문자열도 구하는 것이다.
스페셜 저지 문제이기 때문에 최장 공통 문자열이 여러개가 있으면 아무거나 출력해도 된다.
LCS algorithm은 일반적으로 Longest Common Subsequence를 의미한다.
이 문제도 subsequence를 구하는 문제이다.
주어진 두 문자열의 길이 + 1로 LCS 배열을 생성한다.
LCS 배열을 하나씩 탐색하면서 두 문자가 같으면 좌상단 + 1로 길이를 설정한다.
두 문자가 상이하면 좌측과 상단 중 큰 값으로 길이를 설정한다.
if (strI.charAt(i - 1) == strJ.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]);
Step 1. LCS 배열을 생성한다.
String strI = reader.readLine();
String strJ = reader.readLine();
int[][] lcs = new int[strI.length() + 1][strJ.length() + 1];
Step 2. LCS 배열을 탐색하며 최장 길이를 계산한다.
for (int i = 1; i <= strI.length(); i++)
for (int j = 1; j <= strJ.length(); j++)
lcs[i][j] = strI.charAt(i - 1) == strJ.charAt(j - 1) ?
lcs[i - 1][j - 1] + 1 :
Math.max(lcs[i - 1][j], lcs[i][j - 1]);
Step 3. LCS 배열의 마지막 값부터 탐색하며 최장 길이 문자열을 구한다.
StringBuilder builder = new StringBuilder();
int i = strI.length(), j = strJ.length();
while (lcs[i][j] != 0) {
if (lcs[i][j] == lcs[i - 1][j]) i--;
else if (lcs[i][j] == lcs[i][j - 1]) j--;
else {
builder.append(strI.charAt(--i));
j--;
}
}
-> 실제 문자열은 builder.reverse()를 해야한다.
public void solve() throws IOException {
String strI = reader.readLine();
String strJ = reader.readLine();
int[][] lcs = new int[strI.length() + 1][strJ.length() + 1];
for (int i = 1; i <= strI.length(); i++)
for (int j = 1; j <= strJ.length(); j++)
lcs[i][j] = strI.charAt(i - 1) == strJ.charAt(j - 1) ?
lcs[i - 1][j - 1] + 1 :
Math.max(lcs[i - 1][j], lcs[i][j - 1]);
StringBuilder builder = new StringBuilder();
int i = strI.length(), j = strJ.length();
while (lcs[i][j] != 0) {
if (lcs[i][j] == lcs[i - 1][j]) i--;
else if (lcs[i][j] == lcs[i][j - 1]) j--;
else {
builder.append(strI.charAt(--i));
j--;
}
}
result.append(builder.length());
if (builder.length() != 0) result.append("\n").append(builder.reverse());
}