What is the best way to solve Koko Eating Bananas?

The optimized O(n) approach using Binary Search patterns is generally preferred.

상위 150개 인터뷰쉬움

바나나를 먹는 코코

'코코 먹는 바나나' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

코코는 바나나 먹는 걸 좋아해요. n 바나나 더미가 있고, i번째 더미에는 piles[i] 바나나가 있습니다. 경비원은 떠났고 h시간 후에 다시 올 것입니다.

Koko는 시간당 바나나 섭취 속도를 k로 결정할 수 있습니다. 매 시간마다 그녀는 바나나 더미를 선택하고 그 더미에서 k 바나나를 먹습니다. 더미에 바나나가 k개 미만이면 대신에 바나나를 모두 먹고 이 시간 동안 더 이상 바나나를 먹지 않습니다.

코코는 천천히 먹는 것을 좋아하지만 경비원이 돌아오기 전에 바나나를 모두 먹고 싶어합니다.

그녀가 h 시간 내에 모든 바나나를 먹을 수 있도록 최소 정수 k을 반환합니다.

minEatingSpeed(piles: List[int], h: int) -> int 함수를 작성하세요.

제약

•1 <= len(piles) <= 10^4
•len(piles) <= h <= 10^9
•1 <= piles[i] <= 10^9

예

Example 1

Input

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

Output

Explanation

At speed 4: pile 3 takes 1 hour, pile 6 takes 2 hours, pile 7 takes 2 hours, pile 11 takes 3 hours. Total = 8 hours.

Example 2

Input

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

Output

Explanation

At speed 30: each pile takes 1 hour. Total = 5 hours.

Example 3

Input

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

Output

Explanation

At speed 23: piles take 2+1+1+1+1 = 6 hours.

Need a Hint?

세트나 힙과 같은 이진 검색 관련 데이터 구조를 사용하는 것을 고려해보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

이진 검색 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

import math
def min_eating_speed_opt(piles, h):
    l, r = 1, max(piles)
    res = r
    while l <= r:
        k = (l + r) // 2
        hours = 0
        for p in piles:
            hours += math.ceil(p / k)
        if hours <= h:
            res = min(res, k)
            r = k - 1
        else:
            l = k + 1
    return res

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

import math
def min_eating_speed_brute(piles, h):
    speed = 1
    while True:
        total_time = 0
        for p in piles:
            total_time += math.ceil(p / speed)
        if total_time <= h: return speed
        speed += 1