Longest Increasing Subsequence (python) 풀이

문제 링크 : https://leetcode.com/problems/longest-increasing-subsequence/

Longest Increasing Subsequence - LeetCode

문제 )

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

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

 

정수 배열 nums가 주어질 때, 가장 긴 부분 증가수열의 길이를 반환하세요.

부분 수열은 수열의 순서를 바꾸지 않은 구간 혹은 그 중 일부를 제거한 수열을 말합니다.

예를 들어 [3,6,2,7]은 수열[0,3,1,6,2,2,7]의 부분수열입니다.

 

Constraints:

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

 

해설 )

 수열을 순회하면서 수열의 마지막까지 부분 수열이 증가하는지 검사하는 방식은 O(n^2)의 시간복잡도를 가지므로

이 문제를 해결하는데 적합하지 않습니다.

 

 가장 긴 부분 수열의 길이만을 구하는 문제이므로 문제를 추상화해서 해결할 수 있습니다.

예시로 주어진 수열 nums = [10,9,2,5,3,7,101,18]을 예로 들어 설명해보겠습니다.

처음부터 수열을 탐색하면서 현재 idx까지의 최대 길이를 갖는 부분 수열을 나타내면 아래와 같습니다.

 

 문제의 핵심은 증가 부분수열의 최대 길이만을 구하는 것입니다.

마지막 부분수열처럼 그 요소가 [ 2, 3 7, 18 ] 이나 [ 2, 5, 7, 18 ] 임은 중요하지 않습니다.

부분 수열의 길이가 증가하는 경우는 한 가지로 부분 수열의 마지막 요소가 nums[idx] 보다 작은 경우 뿐입니다.

 

 반대로 부분 수열의 마지막 요소가 nums[idx]보다 큰 경우를 살펴보면

우리는 부분 수열의 마지막 요소를 nums[idx]로 대체해도 아무 문제가 없다는 것을 알 수 있습니다.

예를 들어 idx = 4에서 부분 수열 [ 2, 5 ]를 [ 2, 3 ]으로 대체할 수 있고 이것은 부분 수열의 길이에는 영향을 주지 않습니다.

 

 같은 이유로 부분 수열의 요소 중 nums[idx]보다 큰 요소가 있다면 그것을 nums[idx]로 대체할 수 있음을 직관적으로 이해할 수 있습니다.

 

 이를 코드로 나타내면 아래와 같습니다.

 

from typing import List


class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        arr = [nums[0]]
        for i, num in enumerate(nums[1:]):
            if arr[-1] < num:
                arr.append(num)
            else:
                for j in range(len(arr)):
                    if arr[j] >= num:
                        arr[j] = num
                        break
        return len(arr)