LeetCode 35(Search Insert Position, Python)

1. 문제 링크

• Search Insert Position - LeetCode

Search Insert Position - LeetCode

2. 문제 설명

• 정수가 오름차순으로 정렬된 리스트와 하나의 정수가 주어졌을 때 정수를 리스트에 넣을 위치(오름차순 유지)를 찾아 그 index를 반환하는 문제, 시간 복잡도 O(logn) 으로 풀기
• 예시1) nums = [1,3,5,6], target = 5이면 3과 5 사이에 넣기, index = 2 반환
• 예시2) nums = [1,3,5,6], target = 2이면 1과 3 사이에 넣기, index = 1 반환
• 예시3) nums = [1,3,5,6], target = 7이면 마지막에 넣기, index = 4 반환

3. 처음 풀이

• 쉽게 생각할 수 있는 풀이는 리스트의 처음부터 하나씩 살펴보는 것
  • 리스트 길이를 n이라 하면 최악의 경우 n번 보아야함.
  • 따라서 리스트 길이가 2배가 되면 2배의 연산이 필요
  • 리스트 길이 n에 비례하므로 시간 복잡도가 O(n)이 됨
• 이진 검색
  • 이진 검색은 쉽게 말해 절반씩 날려버리며 확인하는 것인데 훨씬 적은 연산으로 찾을 수 있음
• 예시) [1,2,3,5]에 4를 넣는 상황
  • 1단계 : [1,2], [3,5]로 쪼개고 2보다 4가 크므로 왼쪽 절반을 버리고 [3,5]만 생각
  • 2단계 : [3], [5]로 쪼개고 [3] 보다 4가 크므로 왼쪽 절반을 버리고 [5]만 생각
  • 3단계 : [5]보다 4가 작으므로 [5] 바로 앞이 4의 자리
  • 이 방법은 주어진 리스트의 길이가 2배가 되어도 2배의 연산이 필요하지 않다. 
  • 한 번 날릴 때 절반이 날아가니까 한 번만 더 연산하면 2배의 길이까지 커버가 가능
• 예시) [1,2,3,4,5,6,7,9]에 8을 넣는 상황
  • 1단계에서 [5,6,7,9]가 남고
  • 2단계에서 [7,9]가 남고
  • 3단계에서 [9]가 남고
  • 4단계에서 8의 위치를 확정할 수 있음
  • 따라서 시간 복잡도 O(logn)이 됨

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left=0 #왼쪽 경계를 가장 처음
        right=len(nums) #오른쪽 경계를 가장 마지막
        mid=int((left+right)/2) #왼쪽 오른쪽의 평균을 가운데로

        while len(nums[left:right])!=1: #절반씩 날려서 하나만 남을 때까지 반복
            if nums[left:mid][-1]>=target: #왼쪽의 마지막 값이 target보다 크거나 같으면 오른쪽 절반을 버림
                right=mid #오른쪽을 버리니까 오른쪽 경계를 가운데로
                mid=int((left+right)/2) #가운데를 업데이트
            else: #왼쪽 마지막 값이 target보다 작으면 왼쪽 절반을 버림
                left=mid #왼쪽을 버리니가 왼쪽 경계를 가운데로
                mid=int((left+right)/2) #가운데를 업데이트

        if nums[left]<target: #마지막 남은 것이 target보다 작으면 오른쪽에 target을 넣으면 되고
            return right
        else: #마지막 남은 것이 target보다 크면 왼족에 target을 넣으면 된다.
            return left

4. 다른 풀이

등호 넣는 위치가 경계 위치 한칸 정도씩 차이나고 논리는 모두 같음

#다른 사람의 풀이
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)        
        while l<r:
            m = (l+r)//2
            if nums[m]>=target:
                r = m
            else:
                l = m+1
        return l

 

#위키피디아
def binarySearch(array, value, low, high):
	if low > high:
		return False
	mid = (low+high) / 2
	if array[mid] > value:
		return binarySearch(array, value, low, mid-1)
	elif array[mid] < value:
		return binarySearch(array, value, mid+1, high)
	else:
		return mid

5. 배운 점

• 이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)
• 작동 원리는 위에서 말한 것처럼 절반씩 날리는 것
• 장점
  • 시간 복잡도 O(logn)으로 효율 적이며 메모리 사용량이 적음
• 단점
  • 데이터 정렬이 필요하여 데이터 추가나 삭제는 불편함
  • 중복 항목이 있는 경우 그 중 특정 하나를 찾기는 어려움