[LeetCode#300] Longest Increasing Subsequence

 

❐ Description

---

문제 링크	https://leetcode.com/problems/longest-increasing-subsequence/description
난이도	Medium

 

 

 

 

 

❐ Dynamic Programming

---

나의 경우 주어진 nums 배열을 거꾸로 순회하면서 풀이하는 방식으로 접근했다.

우선 memo 배열은 1로 초기화해주었다. 왜냐면 최소 길이가 1 이기 때문이다.

 

작동 방식은 다음과 같다.

// 1. idx = 7
int target = nums[7] = 18
최대 길이는 18 자신이므로 1

// 2. idx = 6
int target = nums[6] = 101
101 다음 숫자가 18로, 101 보다 작기 때문에 현재 위치에서 최대 길이는 1

// 3. idx = 5
int target = nums[5] = 7
7보다 큰 숫자가 nums[6], nums[7]이 있으므로,
`1 + memo[6]`과 `1 + memo[7]`중 큰 수를 memo[5]에 저장한다.

이를 반복한다.

 

결과적으로 memo 배열을 아래와 같이 초기화 될 것이다.

[2, 2, 4, 3, 3, 2, 1, 1]

idx가 2일 때 가장 긴 결과를 반환함을 알 수 있다.

⏱️ 시간 복잡도 : O(n²)

fun main() {
    val solution = KtSolutionV1()
    val nums = intArrayOf(0, 1, 0, 3, 2, 3)
    val answer = solution.lengthOfLIS(nums)
    println(answer)
}

class KtSolutionV1 {
    fun lengthOfLIS(nums: IntArray): Int {
        val memo = IntArray(nums.size) { 1 }
        var max = 1
        for (i in 0..nums.lastIndex) {
            for (k in 0..i) {
                if (nums[k] < nums[i]) {
                    memo[i] = maxOf(memo[i], memo[k] + 1)
                    max = maxOf(memo[i], max)
                }
            }
        }
        return max
    }
}

public class DpSolution {

    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int[] memo = new int[len];
        Arrays.fill(memo, 1);

        int longestSeq = 1;
        for (int i = len - 2; i >= 0; i--) {
            int cIdx = i + 1;
            while (cIdx < len) {
                if (nums[cIdx] > nums[i]) {
                    memo[i] = Math.max(memo[cIdx] + 1, memo[i]);
                    longestSeq = Math.max(longestSeq, memo[i]);
                }
                cIdx++;
            }
        }
        return longestSeq;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};

        DpSolution solution = new DpSolution();
        int answer = solution.lengthOfLIS(nums);
        System.out.println(answer);
    }
}

 

 

 

 

 

❐ Binary Search

---

다른 사람의 풀이를 보고 이해해봤다.

 

이 풀이의 핵심은 다음과 같다.

Binary Search를 통해 res 리스트에서 target이 삽입될 인덱스를 찾는다.

 

작동 방식은 다음과 같다.

int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};

// 1. n = 10
res가 비어 있으므로 추가 → res = [10]

// 2. n = 9
res의 마지막 숫자(10)보다 작으므로 binarySearch로 위치를 찾아 9로 대체 → res = [9]

// 3. n = 2
binarySearch로 위치를 찾아 2로 대체 → res = [2]

// 4. n = 5
res의 마지막 숫자(2)보다 크므로 추가 → res = [2, 5]

// 5. n = 3
binarySearch로 위치를 찾아 3으로 대체 → res = [2, 3]

// 6. n = 7
res의 마지막 숫자(3)보다 크므로 추가 → res = [2, 3, 7]

// 7. n = 101
res의 마지막 숫자(7)보다 크므로 추가 → res = [2, 3, 7, 101]

// 8. n = 18
binarySearch로 위치를 찾아 18로 대체 → res = [2, 3, 7, 18]

⏱️ 시간 복잡도 : O(nlogn)

public class BinarySearchSolution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> res = new ArrayList<>();
        
        for (int num : nums) {
            if (res.isEmpty() || res.getLast() < num) {
                res.add(num);
            } else {
                int idx = binarySearch(res, num);
                res.set(idx, n);
            }
        }
    }
    
    private int binarySearch(List<Integer> res, int target) {
        int left = 0;
        int right = res.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (res.get(mid) == target) {
                return mid;
            } else if (res.get(mid) > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
    
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};

        BinarySearchSolution bs = new BinarySearchSolution();
        int answer = bs.lengthOfLIS(nums);
        System.out.println(answer);
    }
}

 

 

 

 

 

---