BST: 875. Koko Eating Bananas ★

875. Koko Eating Bananas

 

https://youtu.be/U2SozAs9RzA?si=lxNzqfZ1jL_lzHUX

 

from math import ceil
from typing import List

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # 이진 탐색 범위 설정
        # 최소 속도는 1 (최소 한 개라도 먹음), 최대 속도는 max(piles) (한 번에 가장 큰 더미를 모두 먹음)
        # Set the binary search range:
        # Minimum speed is 1 (at least one banana per hour), and maximum speed is max(piles) (eating the largest pile in one hour).
        l, r = 1, max(piles)

        # 이진 탐색 수행
        # Perform binary search
        while l <= r:
            mid = (l + r) // 2  # 현재 속도(mid)를 이진 탐색 중간값으로 설정
            # Set the current speed (mid) as the middle value of the binary search range.
            pred_h = sum(ceil(p / mid) for p in piles)  # 현재 속도로 먹는 데 걸리는 총 시간 계산
            # Calculate the total time required to eat all bananas at the current speed.
            # ceil() 함수는 올림 연산, The ceil() function performs the ceiling operation (rounding up).			

            if pred_h <= h:
                # pred_h가 h보다 작거나 같으면 조건을 만족
                # => 가능한 k 중에서 더 작은 값을 찾기 위해 r을 줄임
                # "작거나 같다" 조건은 pred_h == h뿐만 아니라 pred_h < h인 경우도 유효한 k를 포함시켜야 함
                # 이 조건을 포함하지 않으면 최소의 k를 놓칠 수 있음
                # If pred_h is less than or equal to h, it means the condition is satisfied.
                # Reduce the search range (move r) to find smaller valid k values.
                # The "less than or equal" condition ensures we include cases where pred_h < h.
                r = mid - 1
            else:
                # pred_h가 h보다 크면 조건을 만족하지 못함
                # => 더 큰 k를 찾아야 하므로 l을 늘림
                # If pred_h is greater than h, the current speed is too slow.
                # Increase the search range (move l) to find larger k values.
                l = mid + 1

        # 이진 탐색이 끝난 후 l이 최소 속도(k)가 됨
        # Once the binary search is complete, l will be the minimum speed (k).
        return l