[LeetCode]Search Insert Position

https://leetcode.com/problems/search-insert-position/

Search Insert Position - LeetCode

 

문제 분석

target으로 주어지는 숫자가 nums 배열에 삽입되는 경우 예상되는 index를 구하는 문제입니다.

 

처음 시도한 답안 O(n)

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target <= nums[0]:
            return 0

        for idx, value in enumerate(nums[:-1]):
            if value <= target and target <= nums[idx+1]:
                return idx+1

        return len(nums)

접근 방법

1. target이 nums의 첫번째 요소보다 작으면 0을 return 합니다.
2. nums 를 순회합니다.
3. target이 해당 시점의 value와 다음 value 사이의 값이라면 인덱스 + 1 을 return 합니다.
4. 모두 만족하지 못한다면 맨 뒤에 위치하는 것이므로 nums의 길이값을 return 합니다.

문제자체는 nums 리스트를 n번 순회하면 풀리기 때문에 어렵지 않았으나, 제약조건으로 O(log n)이 나와 있었기에 최적화가 필요했습니다. 통상적으로 n의 값이 커지면 커질수록 O(n)에 비해 O(log n)이 빠릅니다.

 

두번째로 시도한 답안 O(log n)

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # Binary Search O(log N)
        left = 0
        right = len(nums) - 1

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

            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return left

접근 방법

1. Binary Search(이진 탐색)를 활용합니다.
2. left 값이 right 값보다 크거나 같은 경우에만 반복합니다.
3. mid 값을 구하고 target과 비교합니다.
4. mid보다 target이 크다면, left를 mid+1로 이동합니다.
5. mid보다 target이 작거나 같다면, right를 mid-1로 이동합니다. 
6. 이진 탐색을 활용하면 right가 left보다 왼쪽에 위치할 때 끝나게 되므로 left 혹은 right+1 값을 return 합니다.

Binary Search 알고리즘을 활용해 O(log n)으로 시간 복잡도를 줄일 수 있었습니다. 처음에 문제를 풀때는 이진 탐색을 전혀 떠올리지 못했는데 관련 유형을 여러번 복습해야 생각해낼 수 있을 것 같습니다.