[JAVA] 백준 9252 LCS, DP

 

 

 

9252번: LCS 2

문제

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

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

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

풀이

두 개의 문자열이 주어졌을 때 LCS의 길이와 LCS를 출력하는 문제이다.

찾아보니 LCS를 DP로 효율적으로 푸는 방법이 있었고 해당 방법을 통해서 문제를 해결하였다.

📌 DP 배열 만들어주기

        long[][] A = new long[value1.length+1][value2.length+1];
        for(int i=1; i<A.length; i++){
            for(int j=1; j<A[0].length; j++){
                A[i][j] = value1[i-1] == value2[j-1] ? A[i-1][j-1] + 1 : Math.max(A[i-1][j], A[i][j-1]);
            }
        }

• A[i][j]는 현재 문자열 인덱스 i-1, j-1가 서로 같다면 이전 값에서 1을 더해주고 그게 아니라면 A[i-1][j], A[i][j-1]의 값 중 큰 값을 선택하여 만들어준다.
• 이렇게 만들어진 2차원 배열의 끝에 LCS의 길이가 나오게된다.

📌 LCS 문자열 구하기

        String answer = "";
        int x = value1.length;
        int y = value2.length;
        while (x > 0 && y > 0){
            if(value1[x-1] == value2[y-1]){
                answer = value1[x-1] + answer;
                x--;
                y--;
            }else {
                if (A[x - 1][y] <= A[x][y - 1]) {
                    y--;
                } else {
                    x--;
                }
            }
        }

다음과 같은 규칙을 통해서 LCS 문자열을 구할 수 있다.

1. 만약 현재 문자열 인덱스의 문자가 서로 같다면 정답 문자열에 추가해주고 대각선으로 이동한다.
2. 그렇지 않고 만약 A[x-1][y]가 A[x][y-1]보다 작거나 같다면 y인덱스를 한칸 거슬러 올라간다.
3. 그렇지 않고 만약 A[x-1][y]가 A[x][y-1]보다 크다면 x인덱스를 한칸 거슬러 올라간다.

x 혹은 y가 0보다 클때까지 반복해준다.

📌 전체 코드

import java.util.*;
import java.io.*;

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

        char[] value1 = br.readLine().toCharArray();
        char[] value2 = br.readLine().toCharArray();

        long[][] A = new long[value1.length+1][value2.length+1];
        for(int i=1; i<A.length; i++){
            for(int j=1; j<A[0].length; j++){
                A[i][j] = value1[i-1] == value2[j-1] ? A[i-1][j-1] + 1 : Math.max(A[i-1][j], A[i][j-1]);
            }
        }

        String answer = "";
        int x = value1.length;
        int y = value2.length;
        while (x > 0 && y > 0){
            if(value1[x-1] == value2[y-1]){
                answer = value1[x-1] + answer;
                x--;
                y--;
            }else {
                if (A[x - 1][y] <= A[x][y - 1]) {
                    y--;
                } else {
                    x--;
                }
            }
        }

        System.out.println(A[value1.length][value2.length]);
        System.out.println(answer);
    }

}

결과