[Leetcode/파이썬] 300. Longest Increasing Subsequence

Longest Increasing Subsequence

---

Given an integer array nums, return the length of the longest strictly increasing subsequence.

 

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

 

Constraints:

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

 

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

 

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        def binary_search(res, n) :
            left = 0
            right = len(res) - 1

            while left <= right :
                mid = (left + right) // 2

                if res[mid] == n :
                    return mid
                elif res[mid] > n :
                    right = mid - 1
                else :
                    left = mid + 1
            return left
            
        res = []
        for n in nums :
            if not res or res[-1] < n :
                res.append(n)
            else :
                idx = binary_search(res, n) 
                res[idx] = n
        return len(res)

힌트 부분에 O(n log n) 이라고 적혀있어서 (아 이거 무조건 1/2 씩 줄여나가는 방법을 채용해야 하는구나) 라고 생각했다. 

그러면 선택지는 크게 줄어드는데 바로 이진탐색이다. 함수 부분은 외우는 것이 좋겠다. 

문제 해결 부분에서 res 배열 안에 아무것도 없을 경우나 마지막에 들어간 숫자가 새로 등장한 숫자보다 작을 경우에는 그냥 res에 append 한다. 이후 BS를 통하여 해결을 하게 되는데 마지막 숫자가 새로 들어오는 숫자보다 클 경우, 우리는 숫자를 교체하게 될 것이다. 

1번 예시에서 res 배열은 다음과 같이 변동될 것이다.

[10]
[9]
[2]
[2, 5]
[2, 3]
[2, 3, 7]
[2, 3, 7, 101]
[2, 3, 7, 18]

따라서 숫자 4가 리턴된다. 예시 설명에서는 [2,3,7,101]이 정답이라고 나와있지만, 크게 상관 없는 부분이기 때문에 이렇게 해결 할 수 있을 것이다.