CodeWars 아흔 아홉 번째 문제

Longest Common Subsequence

public static String lcs(String x, String y) {
    int[][] arr = new int[x.length()+1][y.length()+1];

    for(int i = 0; i < x.length() ; i++) {
        for(int j = 0; j < y.length(); j++) {
            if(x.charAt(i) == y.charAt(j)) {
                arr[i+1][j+1] = arr[i][j]+1;
            } else {
                arr[i+1][j+1] = Math.max(arr[i+1][j], arr[i][j+1]);
            }
        }
    }

    String substring = "";
    int count = 1;

    for(int j = 1; j < y.length()+1; j++) {
        for(int i = 1; i < arr.length; i++) {
            if(count == arr[i][j]) {
                substring += String.valueOf(y.charAt(j-1));
                count++;
                break;
            }
        }
    }

    return substring;
}

• 얼마전에 substring이랑 subsequnce 메소드 비교하는 블로그를 보다가 LCS 알고리즘을 본적이 있다.
• 그때는 대략 보고 넘겼는데 마침 오늘 LCS 알고리즘 문제가 딱 나왔다.
• LCS 알고리즘을 먼저 이해하고 풀어서 문제는 쉽게 풀었으나 LCS 알고리즘을 이해하는데 조금 시간이 걸렸다.