[Baekjoon Online Judge] 1620번: LCS 2

9252번: LCS 2

요구사항

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

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

입력

 - 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

 - 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

 - LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

---

기존에 풀었던 LCS에서 추가적으로 만족하는 문자열까지 출력하는 문제이다. 처음에 단순히 숫자가 커질 때 마다 문자열을 추가하도록 설정하였는데, 너무 다양한 경우의 수가 있기 때문에 만족하지 않았다. 

 

기존에 dp로 사용한 배열을 활용하여 뒤로 탐색하며 문자열을 붙여서 완성하였다.

 

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

public class Baekjoon9252 {

    private static int[][] dpTable;
    private static String lcs = "";
    private static int max = 0;

    private static void LCS(Character x, int i, Character y, int j) {
        if (i == 0 || j == 0) dpTable[i][j] = 0;
        else if (x == y) {
            dpTable[i][j] = dpTable[i - 1][j - 1] + 1;
        } else if (x != y) {
            dpTable[i][j] = Math.max(dpTable[i][j - 1], dpTable[i - 1][j]);
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        String a = "0" + bufferedReader.readLine();
        String b = "0" + bufferedReader.readLine();
        dpTable = new int[a.length()][b.length()];

        for (int i = 0; i < dpTable.length; i++) {
            for (int j = 0; j < dpTable[0].length; j++) {
                LCS(a.charAt(i), i, b.charAt(j), j);
            }
        }

        bufferedWriter.write(dpTable[a.length() - 1][b.length() - 1] + "\n");

        int x = a.length() - 1; // 6 ACAYKP
        int y = b.length() - 1; // 6 CAPCAK
        StringBuilder stringBuilder = new StringBuilder();
        while (!(x == 0 || y == 0)) {
            if (a.charAt(x) == b.charAt(y)) {
                System.out.println("x: " + x + " | y: " + y + " | string: " + stringBuilder.reverse().toString());
                stringBuilder.append(a.charAt(x));
                --x; --y;
            } else if (dpTable[x][y] == dpTable[x - 1][y]) {
                System.out.println("--x");
                --x;
            } else if (dpTable[x][y] == dpTable[x][y - 1]) {
                System.out.println("--y");
                --y;
            }
        }

        bufferedWriter.write(stringBuilder.reverse().toString());

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}