첫번째 코드
단순하게 직접 찾으면서 비교하면 된다라고 생각했다.
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' 카테고리의 다른 글
Minimum Number of Moves to Seat Everyone (0) | 2024.06.17 |
---|---|
Range Sum of BST (0) | 2024.06.14 |
Counting Bits (0) | 2024.06.11 |
Minimum Number Game (0) | 2024.06.05 |
Maximum Product of Two Elements in an Array (0) | 2024.05.27 |