binarySearch를 정렬된 리스트에 insert를 위해서만 사용한 나 조금 무례할지도 [leetcode]

알고리즘 문제를 풀다 보면 정렬된 배열에서 특정 숫자가 들어갈 자리 찾는 문제를 자주 만나게 된다.

그런 문제들 만날 때마다 ‘아 또 binary search 쓰라는 말이구나’ 하고 기계적으로 코드를 치는데

오늘 만난 문제는 좀 달랐다. 풀이도 신박했어서 그거에 대해서 써보려고 한다.

 

그냥 배열 순회하면서 하나씩 비교하면 금방 찾겠네~ 아 껌이네~ 근데 medium??

 

특이한 요구사항이 하나가 있다.

Your solution must run in O(log n) time and O(1) space.

문제가 단순해 보여서 그런지 머릿속으로는

‘그냥 순회하면서 하나씩 비교하면 바로 나오지 않나?’ 밖에 생각나지 않았다.

그렇지만 그럼 O(n) 이기 때문에…

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        while len(nums) > 1:
            a = nums.pop()
            b = nums.pop()
            if a == b:
                continue
            else:
                return a
        return nums[0]

그런 쉬운 길을 택하는 나란 사람…

끝에서부터 배열에서 두 개씩 꺼내보면서 비교하고 다르면 숫자를 반환하게끔 구현했다.

POP 연산은 O(1)이지만, 최악의 경우 시간 복잡도는 O(n) 이니까…

결론적으로는 O(n)… (어쩔 수 없다 이거밖에 생각 안 나는데…)

일단 이렇게 통과를 받아놓고 도대체 무슨 유형의 문제인지 확인했다.

 

아니 이게 binary search라고?

그래서 솔루션을 통해 확인했다.

기존 binary search와 비슷하게 left, right 두 가지의 포인터를 가지고

mid = (left + right) / 2로 범위를 줄여나가는데

 

다른 점은

인덱스가 짝수인 배열 부분의 숫자와 해당 인덱스의 +1 된 옆 숫자를 비교했을 때

1. 다르다면 right = mid로 치환
2. 같다면 해당 인덱스의 아랫부분은 정렬과 숫자 중복이 제대로 된 거니 left = mid + 2

코드로 보자.

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        
        left = 0
        right = len(nums)-1
        answer = -1
        while left < right:
            mid = (left+right) // 2
            
            if mid % 2 != 0:
                mid -= 1
            if mid+1 < len(nums) and nums[mid] != nums[mid+1]:
                right = mid
            else:
                left = mid+2
        answer = nums[left]
        return answer

근데 별로 안 빠르다...

 

** 2023-02-26 추가적으로 작성!! **

 

위 문제를 푸니 leetcode는 또 여러 비슷한 문제를 추천해 줬다.

그래서 binarySearch 류의 문제들 정리~

011. Capacity To Ship Packages Within D Days

 

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages 
in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, 
so using a ship of capacity 14 and splitting the packages 
into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

처음엔 dynamic programming인 줄 알고 열심히 고민했는데 전혀 모르겠어서 유형을 보니 이것 역시 Binary Search…

capacity의 최솟값과 최댓값을 각각 구한 뒤, 가능한 capacity를 체크하면서 범위를 반절씩 줄여나가면 된다.

여기서 중요한 포인트!

1. 최소, 최대를 설정한다.
2. 문제에서 설정된 조건, 상황에 맞는지 체크한다.
3. 범위를 반절로 줄인다.

binarySearch는 위 3가지 조건을 이용하는 알고리즘 이었던 것이다.

(중요!! 단순히 정렬된 숫자에 특정 숫자 위치 찾는 알고리즘이 아니라는 얘기)

그럼 다시 위 문제로 돌아가서,

1. 최소, 최대 값 설정
   1. 최솟값은? → 화물들 중 가장 큰 값도 옮길 수 있어야 하므로 화물 무게 중 가장 큰 화물
   2. (위 예시에서는 무게가 10 인 화물을 옮길 수 있어야 하므로 ⇒ 10)
   3. 최댓값은? → 화물의 무게를 다 더한 값(=하루에 옮겨 버릴 수 있는 양…!) (위 예시에서는 전체 무게인 ⇒ 55)
2. 조건에 맞는지 아닌지 여부를 체크할 check 함수를 만들어주기

def check(weight, day): # 무게와 날짜가 들어오면
  total = 0
  for i in range(len(weights)): # 화물을 순회하면서
      if total + weights[i] <= weight: #무게가 화물보다 크면
          total += weights[i] # 무게를 싣기
      else: #무게가 무거워서 못싣으면
          day -= 1 # 날짜를 하루까고,
          total = weights[i] # 배의 무게를 해당 화물무게로 설정
          if day >= len(weights)-i: #만약 남은 화물이 날짜보다 적으면 무조건 옮길수 있기에
              return True
  if day > 0: # 다 옮겨도 날짜가 남았다면?
      return True
  return False

1. 범위를 반절로 줄여서 조건을 탐색 (Binary Search)

left = max(weights)
right = sum(weights)
while left < right:
    mid = (left + right)//2
    if check(mid, days):
        right = mid
    else:
        left = mid + 1
return left

아래는 전체 코드이다.

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def check(weight, day):
            total = 0
            for i in range(len(weights)):
                if total + weights[i] <= weight:
                    total += weights[i]
                else:
                    day -= 1
                    total = weights[i]
                    if day >= len(weights)-i:
                        return True
            if day > 0:
                return True
            return False

        left = max(weights)
        right = sum(weights)
        while left < right:
            mid = (left + right)//2
            if check(mid, days):
                right = mid
            else:
                left = mid + 1
        return left

결과는?

 

2226. Maximum Candies Allocated to K Children

 

Input: candies = [5,8,6], k = 3
Output: 5
Explanation: 
We can divide candies[1] into 2 piles of size 5 and 3, 
and candies[2] into 2 piles of size 5 and 1. 
We now have five piles of candies of sizes 5, 5, 3, 5, and 1. 
We can allocate the 3 piles of size 5 to 3 children. 
It can be proven that each child cannot receive more than 5 candies.

위 문제 역시 아래의 룰을 따라서

1. 최소, 최대를 설정한다.
2. 문제에서 설정된 조건, 상황에 맞는지 체크한다.
3. 범위를 반절로 줄인다.

하나씩 룰대로 따라가면

1. 최소, 최대를 설정

left = max(min(candies)//k,1)
right = sum(candies)//k

1. 조건에 맞는지 체크하는 함수 구현

def check(num, kid):
  temp_candies = candies
  for candy in temp_candies:
      if candy >= num:
          kid -= (candy//num)
          candy %= num
          if kid <= 0:
              return True
  return False

1. 범위를 반절씩 줄인다.

answer = 0
while left < right:
    mid = (left+right) // 2
    ch = check(mid, k)
    if ch:
        answer = mid
        left = mid+1
    else:
        right = mid

중간중간 예외 사항들도 처리해 준다.

만약 모든 candies를 더해도 사람수보다 적다면 불가능

모든 candies를 더했을 때 사람수와 같다면 딱 1개씩만 배분 가능 (위 binary Search 알고리즘을 탈 필요가 없다)

if sum(candies) < k:
    return 0
elif sum(candies) == k:
    return 1

마지막에 left < right 조건을 만족하지 못해 while문을 빠져나왔을 때

left를 마지막으로 검사해준다.

if check(left, k):
    return left

전체 코드는 아래와 같다.

class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int:
        def check(num, kid):
            temp_candies = candies
            for candy in temp_candies:
                if candy >= num:
                    kid -= (candy//num)
                    candy %= num
                    if kid <= 0:
                        return True
            return False
        
        if sum(candies) < k:
            return 0
        elif sum(candies) == k:
            return 1
        
        left = max(min(candies)//k,1)
        right = sum(candies)//k

        answer = 0
        while left < right:
            mid = (left+right) // 2
            ch = check(mid, k)
            if ch:
                answer = mid
                left = mid+1
            else:
                right = mid
                
        if check(left, k):
            return left
        return answer

결과는