백준 9252 LCS 2 java

문제 소개 www.acmicpc.net/problem/9252

내용

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

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

입력

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

출력

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

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

해결 방법

아이디어

이 방법을 해결하는 아이디어는 LCS 1 문제에서 했던 것처럼 int배열로 DP가 아닌 String 배열로 DP로 만드는 것이다.

-------
LCS 1의 내용
DP를 이용하여 LCS를 구한다. int형 dp[first.length() + 1][second.length() + 1] 를 생성한다.

각 dp 배열의 값에는 여태까지의 LCS의 개수값이 들어간다.

이후에 이중 반복문으로 first와 second의 각 자리수가 같은지 확인하면서 

first.chatAt(i)와 second.charAt(j)가 같으면 dp[i -1][j - 1] 까지의 값에서 + 1한 값을 넣어주고 

다르면 dp[i-1][j]와 dp[i][j - 1]값 중 큰값을 넣어주는 방식으로 해결할 수 있다.

--------

LCS 2는 LCS의 문자열 수와 문자열을 출력하는 것으로 String 배열 DP를 만들어서 문자열의 수는 해당 배열의 값의 legnth()를 통해서 얻을 수 있다. 

실제 풀이 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String first = br.readLine();
        String second = br.readLine();

        String[][] stringDP = new String[first.length() + 1][second.length() + 1];
        Arrays.fill(stringDP[0], "");

        for (int i = 1; i < first.length() + 1; i++) {
            Arrays.fill(stringDP[i], "");
            for (int j = 1; j < second.length() + 1; j++) {
                if (first.charAt(i - 1) == second.charAt(j - 1)) {
                    stringDP[i][j] = stringDP[i - 1][j - 1] + first.charAt(i - 1);
                } else {
                    if (stringDP[i - 1][j].length() > stringDP[i][j - 1].length()) {
                        stringDP[i][j] = stringDP[i - 1][j];
                    } else {
                        stringDP[i][j] = stringDP[i][j - 1];
                    }
                }
            }
        }

        System.out.println(stringDP[first.length()][second.length()].length());
        System.out.println(stringDP[first.length()][second.length()]);
    }
}

결과