[백준] 9252번 - LCS 2 (Gold 4)

문제 링크

백준 9252번 - LCS 2 (Gold 4)

문제 설명

두 수열이 주어졌을 때 모두의 부분 수열이 되는 수열 중 가장 긴 것을 구하시오.
이 문제는 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제라고 불린다.
첫 줄에는 LCS의 길이를, 두번째 줄에는 LCS를 출력하는데 LCS의 길이가 0이라면 둘째줄은 출력하지 않는다.
또한, LCS가 여러 가지라면 아무거나 한 가지만 출력하면 된다.

정답 코드 및 설명

DP를 사용하여 풀 수 있다.
수열 a[]의 i번째 수까지로 이루어진 부분수열과 수열 b[]의 j번째 수까지로 이루어진 부분수열의 LCS 길이를 L[i][j]라고 두자. 그러면 아래와 같은 점화식을 세울 수 있다.
$ L[i][j] = \cases{ L[i - 1][j - 1] + 1 & \text{if} \; a[i] = b[j] \cr \textrm{max}(L[i - 1][j], L[i][j - 1]) & \text{otherwise} }$

이 점화식을 구현하여 LCS의 길이를 구한 것이 14 ~ 25행의 lcsLength 메소드이다.

이제 LCS 수열을 어떻게 역추적하여 구해낼 것인지를 생각해보자.
두 수열 a[], b[]의 끝에서부터 역추적하는 것이 접근에 용이하다.
L 행렬의 값이 1 늘어나는 부분이 결국 LCS 수열에 항이 추가되는 부분이므로, L 행렬의 값이 같은 부분을 따라서 쭉 이동해도 상관없다. 이를 구현한 것이 코드의 32 ~ 39행이다.

L 행렬의 값이 바뀌는 부분을 만났다면, 해당하는 항을 LCS에 추가해주어야 한다.
우리는 수열의 끝에서부터 출발했으므로, 해당하는 항은 현재 LCS의 앞에 들어와야한다.
이를 구현한 것이 코드의 40 ~ 42행이다.

이 떄까지 쭉 말로 설명했는데, 이해하기 쉽도록 예시를 들어보자.
문제에 주어진 예시인 ACAYKP, CAPCAK를 생각하자. 위의 점화식을 통해 행렬을 만들면 아래와 같다.

	C	A	P	C	A	K
A	0	1	1	1	1	1
C	1	1	1	2	2	2
A	1	2	2	2	3	3
Y	1	2	2	2	3	3
K	1	2	2	2	3	4
P	1	2	3	3	3	4

i = j = 6부터 시작한 역추적 과정은 아래와 같다.

1. L[6][6] = L[5][6] = 4이므로, i = 5, j = 6으로 이동한다.
2. L[5][6]은 어느 방향으로 이동해도 3으로 감소한다. LCS에 a[5] = b[6] = K를 추가하고, i = 4, j = 5로 이동한다. 현재 LCS = “K”이다.
3. L[4][5] = 3부터 시작해서 2를 만나기 전까지 최대한 이동하면 L[3][5] = 3에 도달한다.
4. L[3][5]는 어느 방향으로 이동해도 2로 감소한다. LCS에 a[3] = b[5] = A를 추가하고, i = 2, j = 4로 이동한다. 현재 LCS = “AK”이다.
5. L[2][4]는 어느 방향으로 이동해도 1로 감소한다. LCS에 a[2] = b[4] = C를 추가하고, i = 1, j = 3으로 이동한다. 현재 LCS = “CAK”이다.
6. L[1][3] = 1부터 시작해서 0을 만나기 전까지 최대한 이동하면 L[1][2] = 1에 도달한다.
7. L[1][2]는 어느 방향으로 이동해도 0으로 감소한다. LCS에 a[1] = b[2] = A를 추가하고, i = 0, j = 1로 이동한다. 현재 LCS = “ACAK”이다.
8. i = 0에 도달했으므로 역추적이 끝났다. LCS로 “ACAK”를 출력한다.

전체 코드는 아래에 첨부하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ9252 {
    String str1, str2;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str1 = br.readLine();
        str2 = br.readLine();
    }

    int[][] lcsLength() {
        int[][] lcsLength = new int[str1.length() + 1][str2.length() + 1];
        for (int i = 0; i < str1.length(); i++) {
            for (int j = 0; j < str2.length(); j++) {
                if (str1.charAt(i) == str2.charAt(j))
                    lcsLength[i + 1][j + 1] = lcsLength[i][j] + 1;
                else lcsLength[i + 1][j + 1] = Math.max(lcsLength[i + 1][j], lcsLength[i][j + 1]);
            }
        }
        System.out.println(lcsLength[str1.length()][str2.length()]);
        return lcsLength;
    }

    void lcs(int[][] lcsLength) {
        StringBuilder sb = new StringBuilder();
        int i = str1.length();
        int j = str2.length();
        while (i > 0 && j > 0) {
            if (lcsLength[i][j] == lcsLength[i][j - 1]) {
                j--;
                continue;
            }
            if (lcsLength[i][j] == lcsLength[i - 1][j]) {
                i--;
                continue;
            }
            sb.insert(0, str1.charAt(i - 1));
            i--;
            j--;
        }
        System.out.println(sb);
    }

    void solution() throws IOException {
        input();
        lcs(lcsLength());
    }

    public static void main(String[] args) throws IOException {
        new BOJ9252().solution();
    }
}