[ 백준 ] 9252 LCS 2

codesver·2023년 3월 6일
0

Baekjoon

목록 보기
38/72
post-thumbnail

Link | 백준 9252번 문제 : LCS 2

📌 About

전형적인 LCS(Subsequence) 문제이다.

다만, LCS 1 문제와 차이점은 최장 길이 뿐만이 아니라 최장 공통 문자열도 구하는 것이다.

스페셜 저지 문제이기 때문에 최장 공통 문자열이 여러개가 있으면 아무거나 출력해도 된다.

📌 Algorithm

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]);

📌 Solution

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()를 해야한다.

📌 Code

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());
}
profile
Hello, Devs!

0개의 댓글