[파이썬 PYTHON] LeetCode【Longest Increasing Subsequence】

class Solution(object):
    def lengthOfLIS(self, nums):

        # 원소가 들어갈 위치 찾기
        def bs(sub,target):
            left = 0
            right = len(sub)-1
            
            while left<=right:
                mid = (left+right)//2
                if sub[mid] < target:
                    left = mid+1
                else:
                    right = mid-1
            return left
        sub = [nums[0]]
        
        for i in range(1,len(nums)):
            if sub[-1]<nums[i]:
                sub.append(nums[i])
            else:
                idx = bs(sub,nums[i])
                sub[idx]=nums[i]
        return len(sub)

 

예제처럼 

 [10, 9, 2, 5, 3, 7, 101, 18] 이 있다고 할때, 부분집합을 증가하게끔 계속 업데이트하는 방식을 사용하면 된다.

 

1. 첫 원소인 10은 비교 대상이 없으므로 바로 추가한다.

sub = [10]

 

2. 두번째 원소인 9는 10보다 작고 증가하는 부분집합을 만들 수 없기 때문에 10을 제외하고 9로 업데이트한다.

sub = [9]

 

3. 세번째 원소인 2는 9보다 작고 증가하는 부분집합을 만들 수 없기 떄문에 9를 제외하고 업데이트한다.

sub = [2]

 

4. 네번째 원소인 5 는 2보다 커서 증가하는 부분집합을 만들 수 있기 때문에 추가한다.

sub = [2, 5]

 

5. 다섯번째 원소인 3은 5보다는 작지만 2보다는 크다. 따라서 5대신 3으로 원소를 업데이트한다.

sub = [2, 3]

 

6. 여섯번째 원소인 7 은 3보다 크므로 바로 추가한다.

sub = [2, 3, 7]

 

7. 일곱번째 원소인 101보 7보다 크므로 바로 추가한다.

sub = [2, 3, 7, 101]

 

8. 여덟번째 원소인 18은 101보다는 작지만 7보다는 크므로 101대신 18로 업데이트한다.

sub = [2, 3, 7, 18]

 

만들 수 있는 증가하는 부분 집합은 [2, 3, 7, 18] 이 된다.

 

원리는, 부분집합을 증가할 수 있도록 계속 업데이트하는 것이고

 

그러기 위해서는 이분탐색을 통해서 교체해야할 인덱스를 찾아야한다. 

 

파이썬에서 제공하는 bisect_left() 함수로 위치를 찾을 수도 있지만, 함수를 직접 작성해서 구현하였다.