백준 - LCS 2

코드

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();


        int[][] dp = new int[s1.length()+1][s2.length()+1];

        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                dp[i][j] = s1.charAt(i - 1) == s2.charAt(j - 1) ?
                        dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        System.out.println(dp[s1.length()][s2.length()]);
        System.out.println(findLCS(dp,s1, s2));

    }


    private static String findLCS(int[][] dp,String s1, String s2) {
        StringBuilder sb = new StringBuilder();

        int row = s1.length();
        int col = s2.length();

        while (row > 0 && col > 0) {
            if (dp[row][col] == dp[row-1][col]) {
                row--;
            } else if (dp[row][col] == dp[row][col-1]) {
                col--;
            } else {
                sb.append(s1.charAt(row-1));
                row--;
                col--;
            }
        }
        return sb.reverse().toString();
    }
}

풀이

🤔LCS에서 더 나아가서 해당 LCS를 직접 찾아야 하는 문제입니다.
LCS를 dp로 풀었다는 가정하에 생각해보면 LCS에 값을 넣는 경우는 dp[i][j] = s1.charAt(i - 1) == s2.charAt(j - 1)로 두개의 문자가 같은 경우에 dp[i-1][j-1]에 1을 더한 값을 넣어주었습니다.

이를 역추적한다면 해당 LCS를 찾을 수 있습니다.

1. LCS의 dp배열 값 구하기 (백준 - LCS 1의 풀이 방식과 동일)
2. 해당 배열의 마지막 dp[s1.length][s2.length]에서 시작 위,왼쪽의 값과 현제 dp[i][j]의 값이 같다면 해당 위치로 이동 다를 경우 dp[i-1][j-1]로 이동 하면서 해당 배열의 값을 정답값에 넣어주기
3. 위 과정을 반복
4. 현재 StringBuilder에는 답이 거꾸로 들어가 있기에 sb.reverse()로
   값을 반환

LCS에 대해서 잘 모르시겠다면 velog - [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence를 참고하시면 좋을 것 같습니다.

출처 : 백준 - 9252번