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

 

 

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # 가드는 h 시간 후에 돌아옴
        # 코코는 시간당 k 개만큼 먹음
        # 최소 k 개 찾는 것
        # 올림 연산 필요
        piles.sort()

        # 최소, 최대
        l, r = 1, piles[-1]

        def pred_hours(k):
            hour = 0
            for p in piles:
                hour += ceil(p/k) # 올림연산
            return hour

        while l<=r:
            mid = (l+r)//2
            pred_h = pred_hours(mid)

            if pred_h <= h: # 시간이 적게 걸리니, 시간 많이 걸리게 하려면, 개수를 줄여야 함
                r = mid-1
            elif pred_h > h: # 시간이 많이 걸리니, 시간 적게 걸리게 하려면, 개수를 늘려야 함
                l = mid+1

        return l

 

최종 코드

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:

        def predict_hours(k):
            return sum([ceil(p/k) for p in piles])

        # 최소 k 구하기: k는 코코가 1시간에 먹는 바나나 개수
        # 올림연산: ceil()
        l = 1 # 최소 값 세팅, min(piles) 하면 안됨
        r = max(piles) # 최대 값 세팅

        while(l<=r):
            m = (l+r)//2
            pred_h = predict_hours(m)
            if pred_h <= h:
                # 예상시간보다 적게걸리니, 시간을 늘려야 함
                # -> 코코가 적게 먹어야 함
                # -> m 감소
                r = m-1
            else:
                # 시간을 줄여야 함
                # -> 코코가 많이 먹어야 함
                # -> m 증가
                l = m+1          
            
        return l

 

---

---

최종 코드

from math import ceil
class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # k 는 1시간에 먹을수 있는 최대한의 개수, k return
        l, r = 1, max(piles)

        k = float("inf")
        while l<=r:
            m = (l+r)//2
            total = 0
            for p in piles:
                total += ceil(p/m) # 올림연산

            if total <= h:
                # total == h 일때도 k 를 계속 줄일수도 있음
                k = min(k, m)
                r=m-1
            else: # total > h:
                # m을 키워야
                l = m+1
        return k

---

---

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # k 구하는 거
        l=1
        r = max(piles)

        minimum_k = r
        while l<=r:
            k = (l+r)//2
            total = sum([ceil(p/k) for p in piles])
            if total ==h:
                minimum_k = min(minimum_k, k)
                # 같은것을 만족하는 최소 k를 찾아야 하니.
                r = k-1
            elif total > h: # 토털 줄여야 하니깐. k 를 키워.
                l = k+1
            elif total < h: # 토털 키워야 하니깐. k 를 줄여.
                r=k-1
        return minimum_k

✅ 문제 요약 (Koko Eating Bananas – LeetCode 875)

• piles: 바나나 더미 (각 원소는 바나나 개수)
• h: 제한 시간
• k: 시간당 먹는 속도
• ✅ 목표: 최소의 k를 구하되, 주어진 h 시간 안에 모든 바나나를 다 먹을 수 있어야 함

---

❌ 지금 코드의 문제점

이 조건은 total == h인 경우만 정답 후보로 보고 있는데,

사실 total <= h이면 조건을 만족하는 거예요.

---

🧠 왜냐하면?

• k가 커질수록 한 시간에 더 많이 먹으니까 total은 줄어들어요
• 즉, total <= h이면 조건을 만족하는 것
• 우리는 그 중 가장 작은 k를 찾아야 하므로 → 더 작은 k가 있는지 왼쪽으로 탐색해야 해요!

---

✅ 수정된 조건:

if total <= h:
    minimum_k = k
    r = k - 1  # 더 작은 k 찾기 위해 왼쪽 탐색
else:
    l = k + 1  # 시간 초과 → k를 늘려야 함

---

✅ 수정된 전체 코드:

from math import ceil
from typing import List

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l = 1
        r = max(piles)
        minimum_k = r

        while l <= r:
            k = (l + r) // 2
            total = sum([ceil(p / k) for p in piles])

            if total <= h:
                minimum_k = k  # 일단 가능하니까 기록
                r = k - 1       # 더 작은 k가 가능한지 확인
            else:
                l = k + 1       # 시간 초과 → k 키워야 함

        return minimum_k

 

✅ 지금 쓰고 있는 이진 탐색 구조:

if total <= h:
    minimum_k = k
    r = k - 1

여기서 핵심은:

total <= h 라는 조건을 만족한 k는
항상 기존의 minimum_k보다 같거나 작습니다.
왜냐하면 이진 탐색에서 k를 줄여가고 있기 때문이죠.

✅ 요약:

이진 탐색에서 k는 왔다 갔다 하나요?	네, 중간값 k는 오르락내리락할 수 있습니다.
그럼 minimum_k도 왔다 갔다 하나요?	❌ 아닙니다. 조건을 만족하는 작은 쪽으로만 갱신합니다.
그래서 if minimum_k > k:는 필요 없나요?	✅ 필요 없습니다. 이미 더 작은 쪽으로만 가고 있기 때문입니다.

 

---

✅ 예시

piles = [3, 6, 7, 11], h = 8

• k = 4일 때: ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8
• k = 3일 때: ceil(3/3)+ceil(6/3)+ceil(7/3)+ceil(11/3) = 1+2+3+4 = 10 → 시간 초과

답: 4