BOJ_9252_LCS 2_java

https://www.acmicpc.net/problem/9252

9252번: LCS 2

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

/**
 백준 9252번 LCS 2
 골드 4
 */
public class BOJ_9252_LCS2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        solution(str1, str2);
    }

    public static void solution(String str1, String str2){
        int str1Leng = str1.length();
        int str2Leng = str2.length();
        int[][] map = new int[str2Leng+1][str1Leng+1];
        for (int y = 0; y<=str2Leng; y++){
            for (int x = 0; x<=str1Leng; x++){
                if (x == 0 || y == 0){
                    map[y][x] = 0;
                    continue;
                }

                if (str1.charAt(x-1) == str2.charAt(y-1)){
                    map[y][x] = map[y-1][x-1] + 1;
                }else{
                    map[y][x] = Math.max(map[y][x-1], map[y-1][x]);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        int cnt = map[str2Leng][str1Leng];
        int idxy = str2Leng;
        int idxx = str1Leng;
        while (idxy >= 1 && idxx >= 1){
            if (map[idxy][idxx] == map[idxy-1][idxx]){
                idxy--;
            }else if(map[idxy][idxx] == map[idxy][idxx-1]){
                idxx--;
            }else{
                sb.insert(0, str2.charAt(idxy-1));
                idxy--;
                idxx--;
            }
        }

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