[ 알고리즘 ] LeetCode 35. Search Insert Position

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 35. Search Insert Position을 풀고 작성한 글입니다.

문제

요구사항

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

제약사항

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums contains distinct values sorted in ascending order.
• -104 <= target <= 104

풀이

접근법

이진 탐색을 통해 문제를 풀면 된다.

이때 target 값이 nums 배열 내에 존재하지 않을 경우 이진 탐색의 대상이 되는 middle 인덱스 요소의 값이 target 값보다 큰 경우와 작은 경우를 나눠서 생각해야 한다.

먼저 middle 인덱스 요소의 값이 target 값보다 큰 경우 계속해서 범위를 줄여나가며 삽입해야 할 인덱스를 찾아야하기 때문에 end 값을 middle 값에 1 을 뺀 걸로 재할당하고 middle 값을 변수 answer 에 while 반복문이 반복될 동안 계속 재할당한다.

반대로 middle 인덱스 요소의 값이 target 값보다 작은 경우 계속해서 범위를 넓혀나가며 삽입해야 할 인덱스를 찾아야하기 때문에 start 값을 middle 값에 1 을 더한 걸로 재할당하고 middle 값에 1 을 더한 값을 변수 answer 에 while 반복문이 반복될 동안 계속 재할당한다.

나의 풀이

접근법을 토대로 문제를 해결하면 아래와 같다.

def solution(nums: list[int], target: int) -> int:
	start, end, answer = 0, len(nums)-1, 0
	while start <= end:
    middle = (start + end) // 2
    if nums[middle] == target:
    	return middle
	elif nums[middle] > target:
		answer = middle
		end = middle - 1
	else:
    	answer = middle + 1
		start = middle + 1
	return answer

다른 풀이

아래와 같이 파이썬 내장 모듈인 bisect 내에 있는 bisect_left 메서드를 사용하여 문제를 쉽게 풀 수도 있다.

def another_solution(nums: list[int], target: int) -> int:
	from bisect import bisect_left; return bisect_left(nums, target)

시간 복잡도

이와 같이 문제를 풀 경우 시간 복잡도는 문제에서 요구한 것과 같이 O(logN)이다.