백준 9252 자바 - LCS 2

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

9252번: LCS 2

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

코드

import java.io.*;

public class Main {
    private static int[][] dp;
    private static int n, m;
    private static String inputA, inputB;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        inputA = br.readLine();
        inputB = br.readLine();
        n = inputA.length();
        m = inputB.length();

        dp = new int[n + 1][m + 1];
        int result = lcsLength();

        StringBuilder sb = new StringBuilder();
        while (n != 0 && m != 0) {
            if (inputA.charAt(n - 1) == inputB.charAt(m - 1)) {
                sb.insert(0, inputA.charAt(n - 1));
                n--; m--;
            } else if (dp[n][m] == dp[n - 1][m]) {
                n--;
            } else if (dp[n][m] == dp[n][m - 1]) {
                m--;
            }
        }
        bw.write(result + "\n" + sb.toString());
        bw.flush();
    }

    private static int lcsLength() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (inputA.charAt(i - 1) == inputB.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]);
                }
            }
        }
        return dp[n][m];
    }
}

풀이

 LCS 라는 알고리즘으로 풀어야하는 문제다. 이차원 배열을 활용한다. 원래 LCS 같은 경우, 두 문자의 i, j 번째 문자가 다르면 dp[i][j] 에 0을, 같으면 dp[i - 1][j - 1]의 값에 1을 더해 저장한다. 이렇게 저장된 배열에 1, 2, 3, 4 이런 식으로 늘어나는 부분이 원하는 결과를 얻는 경우이다. 하지만 여기서는 계속 이어지지 않고 건너 뛰어도 문자열을 이을 수 있다는 특징이 있다. 이를 고려해 lcsLength() 함수에 if문과 else 문을 작성한다.