BaekJoon(9252)::LCS 2

문제

9252번: LCS 2

문제파악

해당문제 또한 백준1904번의 LCS와 같이 제목에서부터 해답을 전달해주고 있다.

Longest Common Sub-sequence Algorithm(LCS, 최장 공통 부분수열)

해당 문제 또한 LCS를 정리한 위 글을 참조하면 될 것 같다.

문제풀이

import java.util.*;

public class Main {
    static int max(int a, int b){
        return a>b?a:b;
    }

    static void lcs(char[] X, char[] Y, int m, int n){
        int DP[][] = new int[m+1][n+1];
        int lcs_length = 0;
        Stack<Character> stack = new Stack<>();

        for(int i = 0;i<= m; i++) {
            for (int j = 0; j<= n; j++) {
                if (i == 0 || j == 0)
                    DP[i][j] = 0;
                else if (X[i - 1] == Y[j - 1]) {
                    DP[i][j] = 1 + DP[i - 1][j - 1];
                }
                else
                    DP[i][j] = max(DP[i-1][j], DP[i][j-1]);


                lcs_length = max(lcs_length, DP[i][j]);
            }
        }
        System.out.println(lcs_length);

        while(DP[m][n] != 0) {
            if(DP[m][n] == DP[m][n-1]) n--;
            else if(DP[m][n] == DP[m-1][n]) m--;
            else {
                stack.push(X[m-1]);
                m--;
                n--;
            }
        }

        while(!stack.empty()) {
            System.out.print(stack.peek());
            stack.pop();
        }

    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        String str1 = in.nextLine();
        String str2 = in.nextLine();

        char[] X=str1.toCharArray();
        char[] Y=str2.toCharArray();

        lcs(X, Y, str1.length(), str2.length());

    }
}

해당문제는... 처음으로 자바로 문제를 풀어봤는데 앞으로는 최대한 자바로 문제를 풀어보려고 한다.