[LeetCode] 300. Longest Increasing Subsequence | LIM

문제

https://leetcode.com/problems/longest-increasing-subsequence/description/

Longest Increasing Subsequence - LeetCode

 

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

 

Example1

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.

 

Example2

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

 

Example3

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

 

설명

주어진 배열에서 증가하는 부분배열 중 가장 긴 부분배열의 길이를 구하면 된다.

 

푼 방식(Nested for loop -> O(N^2), DP)

1. 1로 채워진 새로운 dp 배열을 생성한다. (for memoization)

2. nums배열을 순회한다.

3. 해당 위치에서 그 전까지 확인하면서 이전 숫자보다 현재 숫자가 더 크면 max(dp[i], dp[j]+1) 로 갱신한다.

 

코드

class Solution:
	def lengthOfLIS(self, nums: List[int]) -> int:
		dp = [1] * len(nums)
		for i in range(1, len(nums)):
			for j in range(0, i):
				if nums[i] > nums[j]:
					dp[i] = max(dp[i], dp[j]+1)
		return max(dp)

 

결과

 

DP 를 이용하긴 했지만 결국 이중 for 문이기 때문에 성능은 그다지 좋지 않다.

 

 

다른풀이

1. 새로운 배열을 생성한다.

2-1. 배열에 값이 아무것도 없으면 nums 배열의 첫 번째 원소를 append 한다.

2-2. 배열에 값이 있는 경우 끝 값과 현재 넣으려는 값을 비교한다.

3-1. 만약 새로운 배열의 끝 값이 현재 값보다 작다면 현재 값을 새로운 배열에 append 한다.

3-2. 새로운 배열의 끝 값이 현재 값보다 크다면 현재 값을 정렬이 망가지지 않게 binarysearch 로 탐색해 적절한 위치에 overwrite 한다.

4. 어차피 부분 배열의 길이를 구하는 문제이기 때문에 배열에 값이 어떤 것이 들어가도 정답에서 신경쓰지 않는다.

 

 

 

코드

class Solution:
    def binary_search(self, sub: List[int], target):
        left = 0
        right = len(sub) - 1
        
        while left <= right:
            mid = (left + right) // 2
            if sub[mid] == target:
                return - 1
            elif sub[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

    def lengthOfLIS(self, nums: List[int]) -> int:
        new = [nums[0]]
        for i in range(1, len(nums)):
            if new[-1] < nums[i]:
                new.append(nums[i])
            else:
                idx = self.binary_search(new, nums[i])
                if idx != -1:
                    new[idx] = nums[i]
        return len(new)

 

 

결과

 

Runtime 이 크게 개선된 모습을 볼 수 있다.

 

---

 

 

📚 참고

https://www.youtube.com/watch?v=on2hvxBXJH4