[LeetCode] 875 | Koko Eating Bananas | Python

---

문제 링크: https://leetcode.com/problems/koko-eating-bananas/

---

문제

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.

---

조건

• 1 <= piles.length <= $10^4$
• piles.length <= h <= $10^9$
• 1 <= piles[i] <= $10^9$

---

내 풀이

이 문제는 보자마자 이분탐색으로 풀어야겠다는 생각이 들었다.

왜냐하면, 1부터 max(piles)까지 하나하나 적용해보면 풀 수 있지만, 그렇게되면 시간이 많이 걸리기 때문이다.

---

코드

from math import ceil

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        start, end = 1, max(piles)
        mid = start
        
        while start < end:
            hours = 0
            
            for pile in piles:
                hours += ceil(pile/mid)
            
            if hours > h:
                start = mid + 1
            else:
                end = mid
            mid = start + (end-start) // 2
                
        return mid