[백준 9252] LCS2

[문제]

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

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

[입력]

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

[출력]

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

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

[풀이]

LCS 최장 공통 부분 수열은 DP로 풀 수 있다.
우선 문자열 2개를 입력을 받은 후 (1) LCS 함수로 LCS길이를 구해주고, (2) getLCS함수로 최장 공통 부분 수열을 구해준다. dp 2차원 배열을 각 입력받은 문자열별로 행과 열에 배치하여 하나의 행에서 열을 비교하여 같은 문자값이 있으면 현재 위치(i, j)에서 (i-1, j-1)값에다가 1을 더한 값을 현재 위치에 놓는다. 그 후 최장 공통 부분 수열은 dp테이블 값이 변하는 곳의 위치를 찾아 추출해내는 식으로 구한다.

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    static int[][] dp;
    static StringBuilder sb = new StringBuilder();

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


        String s1 = br.readLine();
        String s2 = br.readLine();
        
        LCS(s1, s2);	//(1)
        
        getLCS(s1, s1.length(), s2.length());	//(2)

        System.out.println(sb.toString());
    }

    private static void getLCS(String str1, int x, int y) {
        Stack<Character> s = new Stack<>();

        while (x > 0 && y > 0){
            if(x == 0 || y==0) break;

            if(dp[x-1][y] == dp[x][y]){
                x--;
            } else if(dp[x][y-1] == dp[x][y]){
                y--;
            } else{
                s.push(str1.charAt(x-1));
                x -=1;
                y -=1;
            }
        }
        while (!s.isEmpty()) sb.append(s.pop());
    }

    private static void LCS(String str1, String str2) {
        int N = str1.length();
        int M = str2.length();

        dp = new int[N+1][M+1];

        // dp테이블 채우기 (LCS 길이 구하기)
        for(int i=1; i<=N; i++){
            for(int j=1; j<=M; j++){
                if(str1.charAt(i-1) == str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        sb.append(dp[N][M] + "\n");
    }
}