Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.
Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.
Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.
Return the minimum integer k such that she can eat all the bananas within h hours.
Example 1:
Input: piles = [3,6,7,11], h = 8
Output: 4
Example 2:
Input: piles = [30,11,23,4,20], h = 5
Output: 30
Example 3:
Input: piles = [30,11,23,4,20], h = 6
Output: 23
Constraints:
- 1 <= piles.length <= 104
- piles.length <= h <= 109
- 1 <= piles[i] <= 109
한줄해석 :
코코가 바나나를 먹는데, k개씩 먹을 수 있는데, 모든 바나나를 먹는데, 주어진 h 시간이 걸려야 한다.
그런데, k개씩 먹을때, 현재 바나나 묶음을 다 먹어야 다음 바나나 묶음에 손 댈 수 있음.
현재 바나나 묶음이 조금밖에 안남았다고 하더라도, 다음 바나나 묶음을 가져올 수 있음.
KeyIdea :
핵심은 최소k를 binary search를 사용해서 찾는 것이다.
최소 k를 찾아야 하므로, piles 각 원소를 k로 나눴을때, 나오는 값의 합이 target인 h보다 큰지, 작은지 binary search를 통해 찾을 수 있다.
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
def get_hour(x):
# ( n%x != 0 ) 이건 ()안에가 !=가 들어가서 true false로 떨어짐.
# 나머지가 있으면 1을 더해주고 걍 나눠 떨어졌으면 0임.
return sum(n // x + (n % x != 0) for n in piles)
# ret = 0
# for n in piles:
# ret += n // x + (n % x != 0)
# return ret
## 이분탐색 공식은 그냥 외우자.
l, r = 1, max(piles)
while l <= r:
mid = (l + r) // 2
mid_h = get_hour(mid)
if mid_h <= h:
r = mid - 1
else:
l = mid + 1
return l