백준 - LCS 3

백준 - LCS 3

🤔LCS의 응용 문제입니다. 기존에는 2개의 문자열로 LCS를 구하였다면 이번에는 3개의 문자열에 대한 LCS를 구해야 합니다.

그래서 처음에 저는 2개의 LCS를 구하고 나서 해당 LCS와 나머지 문자열에 대한 LCS를 구하면 되겠다고 생각해서 아래와 같이 풀어보았습니다.

첫 번째 시도 (실패)

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

        String s = logicDp(logicDp(s1, s2), s3);
        System.out.println(s);

    }

    private static String logicDp(String s1, String s2) {
        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]);
            }
        }
        return 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();
    }
}

logicDp()를 통해 dp에 값을 넣어 준 후 findLCS()를 통해 역으로 추적하며 해당 문자열들을 찾아서 푸는 방식으로 진행하였습니다.
😭그러나 이 코드를 제출하면 테스트를 통과하지 못하였고 풀다가 다른 분의 자료를 참고하여서 해당 코드로는 통과할 수 없다는 것을 알아내었습니다. 티스토리 lotus lee - BOJ 백준 1958번 LCS 3 (java)의 블로그를 통해 해당 코드의 반례를 알 수 있었습니다.

두 번째 풀이 (성공)

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

        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                for (int k = 1; k <= s3.length(); k++) {
                    if (s1.charAt(i-1) == s2.charAt(j-1) && s2.charAt(j-1) ==s3.charAt(k-1)) {
                        dp[i][j][k] = dp[i-1][j-1][k-1] + 1;
                    } else {
                        dp[i][j][k] = Math.max(dp[i-1][j][k],Math.max(dp[i][j-1][k],dp[i][j][k-1]));
                    }
                }
            }
        }
        System.out.println(dp[s1.length()][s2.length()][s3.length()]);

    }
}

🫡기존 LCS의 풀이와 비슷한 것을 알 수 있습니다. 기존에는 2차원 배열이었다면 하나의 차원을 더 늘려서 3차원으로 만드신 후 기존 LCS 풀이와 동일하게 푸시면 답을 찾을 수 있습니다. (많은 블로그들이 해당 방법과 비슷하게 푸는 것을 보실 수 있습니다.)

참고자료 : 티스토리 lotus lee - BOJ 백준 1958번 LCS 3 (java)
출처 : 백준 - 1958번