[LeetCode/Python] 35. Search Insert Position

35. Search Insert Position

[문제]

• 정렬된 정수 배열 nums와 목표 값 target
• 타겟이 배열에 존재하면 인덱스를 반환
• 존재하지 않으면 정렬된 순서를 유지하면서 삽입될 위치를 반환해야 한다.

---

[문제 조건]

1. 배열 nums는 오름차순으로 정렬되어 있다.
2. 배열의 길이는 0 <= len(nums) <= 10^4이다.
3. 배열의 원소는 -10^4 <= nums[i] <= 10^4이다.
4. 타겟 값은 -10^4 <= target <= 10^4이다.
5. 시간 복잡도는 O(log n)

---

[코드 1]

이진탐색 버전 (시간복잡도 O(log n) )

def search_insert(nums, target):
    left, right = 0, 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

if __name__ == '__main__':
    nums = [1, 3, 5, 6]
    target = 5
    print(search_insert(nums, target))  # 출력: 2

[코드 1 설명]

1. 이진 탐색 사용:
   • left와 right로 배열의 양끝을 설정하고, 중간값 mid를 계산해가며 탐색.
2. 조건 비교:
   • nums[mid] == target이면 인덱스 반환.
   • nums[mid] < target이면 left를 mid + 1로 이동.
   • nums[mid] > target이면 right를 mid - 1로 이동.
3. 타겟이 없는 경우:
   • left가 right보다 커지면 left 위치에 타겟을 삽입해야 하므로 그대로 반환.

---

[코드 2]

순차탐색 버전 (시간복잡도 O(n))

def search_insert(nums, target):
    for i in range(len(nums)):
        # 타겟이 현재 값보다 작거나 같으면 해당 위치 반환
        if nums[i] >= target:
            return i
    # 타겟이 모든 값보다 크다면 마지막 위치 반환
    return len(nums)

if __name__ == '__main__':
    nums = [1, 3, 5, 6]
    target = 5
    print(search_insert(nums, target))  # 출력: 2

[코드 2 설명]

1. 함수 정의:
   • 함수 이름은 search_insert, 매개변수로 nums와 target을 받는다.
2. 순차 탐색:
   • 배열 nums를 순차적으로 탐색하며, 현재 값이 target보다 크거나 같다면 인덱스 i를 반환한다.
3. 모든 값보다 큰 경우 처리:
   • 모든 값이 target보다 작다면, 배열의 길이 len(nums)를 반환하여 맨 뒤에 삽입한다.