Leetcode 875. Koko Eating Bananas with Python

문제

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.

코코는 바나나를 좋아합니다.
바나나가 n개로 나뉘어져 있습니다.
조련사는 h시간 뒤에 돌아온다고 합니다.
코코가 바나나를 한시간에 k개 먹을수 있을때
코코는 한 무더기에서 k개의 바나나를 먹는데,
만약 무더기에서 바나나의 갯수가 k보다 작을경우
그냥 남은것만 먹고 맙니다.
주어진 h시간 안에 모든 바나나를 먹을떄
최소한의 k를 구하세요.

예시

Input: piles = [3,6,7,11], h = 8
Output: 4

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Input: piles = [30,11,23,4,20], h = 6
Output: 23

제한

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

풀이법

이진탐색을 사용합니다.

from typing import List
from math import ceil

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def koko(p: List[int], i: int):
            return sum(ceil(banana/i) for banana in p) <= h
        start = 1
        end = max(piles)
        while True:
            mid = (start + end) // 2
            ans = koko(piles, mid)
            if ans == False:
                start = mid + 1
            else:
                if mid == 1:
                    return 1
                elif koko(piles, mid-1):
                    end = mid - 1
                else:
                    return mid

여기서 포인트는 바로 왼쪽의 가능성을 계산해서 이게 가능하다면 아직 시간당 먹는 갯수를 줄일수 있으니까

이진 탐색 범위를 왼쪽으로 바꿔주는 것입니다.