[LeetCode 풀이/python] 35. Search Insert Position (easy)

문제 설명: 구분되는 (중복이 없는) 정수 값들이 정렬된 배열 nums 과 타겟 값 target 이 주어졌을 때, target 이 배열 안에 존재하면 그 인덱스를 리턴하시오. 배열 안에 존재하지 않는 경우, 만약 정렬 순서에 맞게 타겟 값을 삽입한다면 들어가게 될 위치를 리턴하시오. 

 

(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.)

 

예시 1)

입력: nums = [1,3,5,6], target = 5  -->  출력: 2

 

예시 2)

입력: nums = [1,3,5,6], target = 2  -->  출력: 1

 

예시 3)

입력: nums = [1,3,5,6], target = 7  -->  출력: 4

 

예시 4)

입력: nums = [1,3,5,6], target = 0  --> 출력: 0

 

예시 5)

입력: nums = [1], target = 0  --> 출력: 0

 

제한 조건:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums 는 각기 구별되는(distinct, 중복X) 값들을 포함하고 있으며, 오름차순 정렬되어 있음
• -10^4 <= target <= 10^4

 

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • 주어진 배열이 정렬되어 있으므로 이진 탐색(binary search) 알고리즘을 이용!  -->  중간값 med 과 타겟값 target 을 비교하여 점차 탐색 범위를 반으로 줄여 나가기~
  • 재귀적으로 구현하되, 탐색 대상 배열의 중간값 (의 인덱스) 를 가리키는 med 와 별개로, 원본 배열 기준 인덱스 idx 를 추가적으로 저장 & 업데이트 
  • 중간값 med 를 기준으로 탐색 범위가 줄어드는 방향(pos) 에 따라 idx 값을 업데이트 하는 방식이 달라지므로 구분하여 처리!

 

• 코드 구현

def searchInsert(nums: List[int], target: int) -> int:
    return bin_search(nums, target, 0, True)
    
def bin_search(nums, t, idx, pos=True):
    med = len(nums)//2
    if pos:
        idx += med
    else:
        if len(nums)%2 == 0:
            idx -= med
        else:
            idx -= (med+1)
    
    if t < nums[med]:
        if len(nums) == 1: 
            return idx
        else: 
            return bin_search(nums[:med], t, idx, False)
    elif t > nums[med]:
        if (len(nums) == 1) or (nums[med] == nums[-1]): 
            return idx+1
        else: 
            return bin_search(nums[med+1:], t, idx+1, True)
    else:
        return idx

 

• 결과
  • 기본적으로 이진 탐색 알고리즘을 활용한 덕분에 시간 복잡도 O(log n) 로 무난하게 통과함
  • 하지만... 어렵지 않은 문제인데 처음에 중간값 구하는걸 요상하게 접근해서 삽질 또 삽질... ㅎㅎㅎ

 

[풀이 2안]

• 접근법
  • 동일하게 이진 탐색(binary search) 알고리즘을 이용하되, 탐색 범위가 되는 배열의 맨 앞 인덱스 left & 맨 뒤 인덱스 right 를 이용해서 중간값의 인덱스 med 를 업데이트 해나감...!!
  • 위의 풀이에서는 med, idx 라는 두 변수에 나뉘어 있던 정보가 med 에 담겨있는 셈... ㅎㅎ
•  

 

• 코드 구현

def searchInsert(nums, target):
    left , right = 0, len(nums)-1
    
    while left <= right:
        med = (left + right)//2
        if target < nums[med]:
            right = med - 1
        elif target > nums[med]:
            left = med + 1
        else:
            return med
    return left

 

• 결과
  • 시간 복잡도는 O(log n) 으로 동일하지만 훨씬 깔끔한 코드.... (이진탐색 구현할 땐 m = (l+r)//2 메모...)
  • 두 코드 모두 런타임 48~52ms / 메모리 15.0~15.2MB 범위 안에서 fluctuation 이 있음