[백준] 9252: LCS 2 - JAVA

09 Jul 2023 in Algorithm on 다이나믹 프로그래밍

https://www.acmicpc.net/problem/9252

풀이

LCS(최장 공통 부분 수열)문제.

두 수열이 주어졌을 때 공통된 부분 수열 중 가장 긴 것을 찾는다.

점화식은 다음과 같다. dp[i][0], dp[0][j]는 0으로 채워진 상태로 시작한다.

if (a[i - 1] == b[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]);
}

수열A와 수열B를 한 글자씩 비교한다.

두 문자가 다르다면 dp[i-1][j]와 dp[i][j-1] 중 큰 값으로 하고,

같다면 dp[i-1][j-1] + 1 으로 한다.

이렇게 하면 최장 공통 부분 수열의 길이를 구할 수 있다.

최장 공통 부분 수열 자체를 구하려면 구한 dp배열에서 거꾸로 탐색해야 한다.

dp배열의 가장 마지막 값에서 시작하여 dp[i-1][j], dp[i][j-1] 중 그 값과 같은 값을 찾는다.

같은 값이 있다면 해당 칸으로 이동한다.

같은 값이 없다면 dp[i][j]에 해당하는 글자를 저장하고 dp[i-1][j-1]로 이동한다.

private static void findResult(int r, int c, int idx) {
    if (idx == dp[a.length][b.length]) {
        return;
    }

    if (dp[r][c] == dp[r - 1][c]) {
        findResult(r - 1, c, idx);
    } else if (dp[r][c] == dp[r][c - 1]) {
        findResult(r, c - 1, idx);
    } else {
        result[idx] = a[r - 1];
        findResult(r - 1, c - 1, idx + 1);
    }
}

결과 문자를 담을 result 배열을 만들어 result배열이 꽉 차면 종료했다.

dp[i][j]가 0일 때 종료해도 된다.

참고: https://velog.io/@emplam27/알고리즘-그림으로-알아보는-LCS-알고리즘-Longest-Common-Substring와-Longest-Common-Subsequence

---

메모리: 18712KB

시간: 156ms

언어: Java 11

코드

import java.io.*;

public class Main {
    static char[] a, b, result;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        a = br.readLine().toCharArray();
        b = br.readLine().toCharArray();

        dp = new int[a.length + 1][b.length + 1];
        for (int i = 1; i < a.length + 1; i++) {
            for (int j = 1; j < b.length + 1; j++) {
                if (a[i - 1] == b[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]);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(dp[a.length][b.length]).append("\n");

        result = new char[dp[a.length][b.length]];
        findResult(a.length, b.length, 0);
        for (int i = result.length - 1; i >= 0; i--) {
            sb.append(result[i]);
        }

        System.out.println(sb);
    }

    private static void findResult(int r, int c, int idx) {
        if (idx == dp[a.length][b.length]) {
            return;
        }

        if (dp[r][c] == dp[r - 1][c]) {
            findResult(r - 1, c, idx);
        } else if (dp[r][c] == dp[r][c - 1]) {
            findResult(r, c - 1, idx);
        } else {
            result[idx] = a[r - 1];
            findResult(r - 1, c - 1, idx + 1);
        }
    }

}