7/4 코테 일지 (Range Search 예시)

Range Search 예시

https://neetcode.io/problems/eating-bananas

어떠한 문제를 풀 때, 답의 값의 범위 (최소, 최대)를 알고 있으면 최소 부터 1을 더해가며 for문을 돌리는 것이 아닌, binsear range search를 하는 것이 효과적이다.

 

단순 for문 

class Solution:
    def minEatingSpeed(self, piles, h):
        k = 1
        hours = h + 1
        while (hours > h):
            hours = 0
            for pile in piles :
                hours += int(pile/k) + (pile % k > 0) 
            k = k + 1
        return k - 1

 

binary search range

class Solution:
    def minEatingSpeed(self, piles, h):
        L, R = 1, max(piles)
        current_h = 0
        while (L<=R):
            mid = (L+R) // 2
            result = self.isTimeEnough(piles, mid,h)
            if result == 1:
                L = mid + 1 
            else :
                R = mid - 1
                current_h = mid
        return current_h
    def isTimeEnough(self, piles, number,h):
        hours = 0
        for pile in piles :
            hours += int(pile/ number) + (pile % number > 0) 
        if hours > h :
            return 1 
        else : 
            return 0

 

 

Range Search 예시 2

2805 나무 자르기 

import sys
n, m = map(int,(sys.stdin.readline().rstrip().split(' ')))
t_array = list(map(int,sys.stdin.readline().rstrip().split(' ')))

l, r = 0, max(t_array)

current_height = 0
while (l<=r):
  mid = (l+r) // 2
  total_height = 0
  for height in t_array:
    if height > mid:
      total_height += (height - mid)
      if total_height>= m:
        break
  if total_height >= m : 
    l = mid + 1 
    current_height = mid
  elif total_height < m :
    r = mid - 1
print(current_height)