875. Koko Eating Bananas (Array, Binary Search)

링크 - https://leetcode.com/problems/koko-eating-bananas/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

우리는 n개의 속도로 먹으면 n+1도 가능하고, n개의 속도로 먹는게 불가능하면 n-1도 불가능하다는 점을 사용하여 binary search를 통해 문제를 풀 수 있다. 여기서 중요한 점은 left는 1이 되어야한다는 점, count <=  h 이면 right를 mid로, count > h 이면 left를 mid + 1로 설정해야 한다는 점이다.

Code

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def binary_search(left, right):
            if left == right:
                return left

            mid = (left + right) // 2
            count = 0
            for p in piles:
                count += ceil(p / mid)
            if count <= h:
                return binary_search(left, mid)
            else:
                return binary_search(mid + 1, right)

        return binary_search(1, max(piles))

Complexity

Time Complexity: O(N*logM) N은 piles의 길이이고, M은 piles에 있는 maximum number of bananas이다.

Space Complexity: O(1)