[DSA][Binary Search] 03. Koko Eating Bananas

LeetCode 875

 

03. 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.

 

 

[질문하기]

- 항상 h 안에 바나나를 다 먹을 수 있는 k가 있음이 보장되나요?

 

 

[아이디어]

- Binary Search를 사용하여 k의 후보를 정한 후, 이 k가 주어진 조건을 만족하는지 판단하는 Parametric Search 문제로 바꾸어 접근하자

 

 

[풀이 1] Binary Search

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

        minK = r
        while l <= r:
            mid = l + (r - l) // 2

            res = 0
            for pile in piles:
                res += math.ceil(pile/mid)

            if res <= h:
                minK = mid
                r = mid - 1
            else:
                l = mid + 1
        
        return minK

어떤 속도 k가 정해졌다면 코코가 바나나를 다 먹는 데 걸리는 시간은 각 pile에 대해 pile / k 값을 이용해 계산할 수 있다. 하지만 어떤 수식을 세워서 주어진 시간 안에 다 먹을 수 있는 최소 속도 k를 직접 계산하기는 어렵다.이렇게 정답 후보가 수의 범위로 주어지고, 각 후보 값에 대해 조건을 만족하는지를 판단하는 함수를 정의할 수 있을 때 Parametric Search로의 접근을 의심할 수 있다. Parametric Search란 정답이 어떤 수치적인 값이라는 것만 알 수 있고 그 값을 직접 계산하기는 어려운 경우에 정답 후보를 정렬된 범위로 놓고 결정 문제 (Yes or No)로 바꿔 이진 탐색으로 찾는 기법이다.

 

 

⏱️ 시간복잡도

배열의 최댓값을 m, 배열의 길이를 n이라 하면 logm의 이진탐색에서 길이 n의 배열을 순회하므로 시간복잡도 O(nlogm)이다.

🧠 공간복잡도

추가적인 공간을 사용하지 않고, 주어진 행렬에서 속도를 계산하는 데 필요한 변수만을 사용하기 때문에 O(1)의 공간 복잡도를 갖는다.