[python3] 35. Search Insert Position

풀이 일자: 23.02.20

난이도: [Easy]

분류: [Binary Search]

문제 내용

정렬된 배열과 target이 주어졌을 때 해당 target이 정렬에 있다면 그 위치를 return하고 정렬에 없다면 들어가야 하는 위치를 return하는 문제였고 반드시 logN의 시간복잡도를 가지는 알고리즘을 쓰라고 했다.

 

문제 해결 흐름

1. Linear하게도 풀 수 있고 Binary로 풀 수 있는데 시간복잡도에 대한 제약조건이 존재하므로 Binary만 가능하겠다.

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0; right= len(nums) - 1;

        while(left <= right):
            mid = (left + right)//2;
            if nums[mid] == target:
                return mid;
            elif nums[mid] < target:
                left = mid + 1;
            else:
                right = mid - 1;

        return left;

 

Time Complexity: O(logN)

시간복잡도는 이진탐색의 시간복잡도인 logN을 가지게 된다.

 

Space Complexity: O(1)

left와 right외의 다른 변수를 사용하지 않기 때문에 공간복잡도는 1이다.

 

다른 해결 방식

1. 이번에는 파이썬에서 제공하는 라이브러리 함수를 사용해보자.

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return bisect.bisect_left(nums, target);

=> 내가 작성했던 binarySearch와 같은 방식으로 작동하는 bisect_left라는 함수를 사용하였다.

 

 

문제 링크

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

Search Insert Position - LeetCode