[NeetCode-LeetCode] Longest Common Subsequence JAVA

반응형

728x90

[NeetCode-LeetCode] Longest Common Subsequence - Medium

---

접근

• dp

---

풀이

가장 긴 공통 부분 수열의 길이를 구하는 문제이다. 바로 전에 풀었던 문제와 유사한 형태로 이번에는 숫자가 들어있는 배열이 아닌 문자열을 비교하여 구해야 한다. 예시를 보면 text1 = "abcde", text2 = "ace"라는 입력이 주어졌을 때 가장 긴 공통 부분 수열은 "ace"로 길이인 3이 정답이 된다. text1에서 순서대로 부분 수열을 만들었을 때 "ace"를 만들 수 있기 때문이다. 2차원 dp 카테고리의 문제인 만큼 dp를 사용해 풀면 된다.

    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();

        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                } 
            }
        }

        return dp[m][n];
    }

2차원 배열을 통해 값을 관리해 주면 된다. text1과 text2의 문자를 비교해 같다면 공통 부분 수열을 늘릴 수 있기 때문에 이전 최대 길이에서 1을 더해주고 다르다면 이전 값 중 더 큰 값을 선택한다. 두 문자열에 대해 모든 비교를 수행하기 때문에 문자열의 길이를 고려하지 않고 해결할 수 있다. 

---

전체 코드

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();

        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                } 
            }
        }

        return dp[m][n];
    }
}