리트코드 - 300. Longest Increasing Subsequence

리트코드 - 300. Longest Increasing Subsequence

출처 - https://leetcode.com/problems/longest-increasing-subsequence/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

정수 배열 nums가 주어지면, 엄격하게 증가하는 가장 긴 길이를 반환합니다.

 

 

의사코드

함수 lengthOfLIS(배열 nums)     n = nums.length     배열 dp의 크기를 n으로 설정     dp[0] = nums[0]     len(정답길이) = 1     반복문 시작(i 1부터 n-1까지)         if (nums[i] > dp[len - 1])             dp[len] = nums[i]             길이 += 1         else             idx = 이진탐색(dp, 0, 길이 - 1, nums[i])             dp[idx] = nums[i]         len 리턴     빈복문 종료 함수 이진탐색(dp, left, right, target):     반복문 시작(left > right)         mid = left와 right 사이의 중간 값         if (dp[mid] < target)             left = mid + 1         else             right = mid    left 리턴

 

풀이코드

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int len = 1;

        for (int i = 1; i < n; i++) {
            if (nums[i] > dp[len - 1]) {
                dp[len++] = nums[i];
            } else {
                int idx = binarySearch(dp, 0, len - 1, nums[i]);
                dp[idx] = nums[i];
            }
        }
        return len;
    }

    private int binarySearch(int[] dp, int left, int right, int target) {
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (dp[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

 

코드설명

이진탐색 + dp를 이용한 풀이이다. 문제의 키포인트는 다음과 같다.

 

1. dp배열의 마지막 값보다 큰 값이면 dp 배열에 추가한다.

2. dp배열의 마지막 값보다 작은 값이면 dp배열 내에서 값을 갱신한다.

 

이렇게 딱 두가지를 생각했을 때 그러면 배열의 최대값을 구할 수 없는 것 아닌가 싶을 수 있다.

핵심은 dp배열의 마지막 값보다 큰 값을 추가할 때만 배열 크기를 늘리는 것이다.

 

예시로 int[] nums 가 [4,10,4,3,8,9] 이런 배열이라고 하자.

dp 배열의 처음에는 nums 배열의 첫번째 값을 넣고 len을 1로 놓는다.

이전 값을 비교하기 위해 len - 1 로 인덱스를 놓는다.

(dp배열은 초기화 되었으므로 모든 배열은 0으로 초기화 되어있지만 편의상 생략한다.)

nums 1부터 반복문을 순회하는데, 10은 4보다 크므로 dp배열의 뒤에 10을 추가하고, len을 2로 추가한다.

다음 배열값은 또 4다. dp 배열 마지막인 10보다 작으므로, 이 값이 갱신될 수 있는 곳을 찾는다.

제일 앞에 값으로 갱신 할 수 있다. len은 증가하지 않는다.

다음으로 3이다. dp배열의 마지막 값보다 작으므로 다시 dp 배열 내에서 갱신될 수 있는 곳을 찾는다.

맨 처음 값인 4보다 작으므로 이 값을 갱신해준다. 역시 len은 증가하지 않는다.

같은 방법으로 8도 10보다 작으므로, dp 배열 내에서 갱신할 값을 찾으면 된다.

dp 배열의 10보다 작은 값이므로 갱신될 수 있다.

dp 배열의 값이 추가된 것이 아니므로 len은 역시 갱신되지 않는다.

다음으로 9는 dp배열의 끝인 8보다 크므로 갱신할 수 있다. len도 추가되어 3이 된다.

이렇게 하면 문제에서 요구하는 '엄격하게 증가하는 배열'에 대한 길이인 len을 구할 수 있다.

 

for (int i = 1; i < n; i++) {
    if (nums[i] > dp[len - 1]) {
        dp[len++] = nums[i];
    }
}

코드에서 for문 안에 if문이 dp배열의 마지막 값을 갱신하는 과정 이고,

else {
    int idx = binarySearch(dp, 0, len - 1, nums[i]);
    dp[idx] = nums[i];
}

else분기는 dp배열 내에서 갱신할 값을 찾는 과정이다. 여기서 이진탐색으로 시간을 줄인 것이다.

 

시간복잡도 - O(n log n)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

초기코드

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int count = 1;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        for (int cur = 0; cur < n; cur++) {
            for (int prev = 0; prev < cur; prev++) {
                if (nums[cur] > nums[prev] && dp[prev] + 1 > dp[cur]) {
                    dp[cur] = dp[prev] + 1;
                    count = Math.max(count, dp[cur]);
                }
            }
        }
        return count;
    }
}

처음에는 dp배열을 1로 가득 채운다음, 현재값과(cur) 이전값(prev)을 만들어서 계속 비교하는 방식을 택했었다.

그렇지만 이렇게 하니 시간복잡도가 O(n^2)으로 너무 오래 걸렸고, 문제에서 제시한 O(n log n) 방식이 아니었다.

 

이진탐색과 dp를 처음 같이 사용해 본 좋은 문제였다.

 

정리

배열을 탐색 할 때 조건에 따라 탐색이 필요한 경우 dp배열을 활용할 것