Search Insert Position

첫번째 코드

 

단순하게 직접 찾으면서 비교하면 된다라고 생각했다.

 

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        count = 0
        for i in nums:
            if i < target:
                count += 1
            elif i == target:
                return count
            elif i > target:
                return count

 

시간초과

---

두번째 코드

 

시간 초과가 문제가 되므로 찾는 것을 더 적게 해야한다.

이때 이진탐색을 이용하면 탐색에 더 적은 시간이 걸린다.

 

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

통과!

---

링크

https://github.com/ornni/leetcode/tree/main/0035-search-insert-position

leetcode/0035-search-insert-position at main · ornni/leetcode