Koko Eating Bananas - Python Solution [LeetCode Medium]

원문

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. --- Example 1) Input: piles = [3,6,7,11], h = 8 Output: 4 Example 2) Input: piles = [30,11,23,4,20], h = 5 Output: 30 Example 3) Input: piles = [30,11,23,4,20], h = 6 Output: 23

 

해석

바나나 더미 n개가 있고 그 더미의 i번째에는 piles[i]개의 바나나가 들어있다. 경비원이 외출했다가 h 시간 후에 돌아올 예정이다. 바나나를 좋아하는 코코는 경비원이 외출할 동안 바나나를 전부 먹으려고 한다.

 

코코는 1시간 동안 먹을 속도를 정할 수 있는데, 1시간 동안 먹을 양을 k라고 한다. 각 시간 동안 코코는 바나나 더미 중에서 하나를 선택하여 그 더미를 먹기 시작할 것이다. 만약 더미에 남아있는 바나나의 양이 먹을 양(k) 보다 적다면 남아있는 바나나를 다 먹고 기다린다. 바나나가 부족해서 남는 시간 동안 다른 더미의 바나나를 먹지 못한다.

 

코코는 경비원이 돌아오기 전까지 모든 바나나를 최대한 시간을 끌면서 느긋하게 먹고 싶다. h시간 안에 모든 바나나를 먹을 수 있는 k 값 중에서 최솟값을 구해서 리턴해라.

 

---

문제 들어가기 전 정리

• n의 길이를 가지고 더미 안에 있는 바나나의 개수 정보가 담긴 리스트 piles가 주어진다.
• 경비원의 외출시간 h가 주어진다.
• 한 시간 동안 하나의 더미에만 손을 댈 수 있다.
• 조건에 맞는 k 중에서 최솟값을 찾아야 한다.

 

Brute Force

1. k의 값에 1, 2, 3, ... , 계속 늘려가면서 대입한다.
2. 그 k값으로 h시간 안에 모든 바나나를 먹을 수 있는지 계산한다.
3. 처음으로 2번 조건에 만족한 k값을 리턴한다.

이 방법을 사용해서 제출하면 당연히 Time Limit Exceeded 가 나온다. 바이너리 서치 알고리즘을 이용하여 시간을 단축시켜 보자.

 

Binary Search

1. left pointer를 1, right pointer를 max(piles)로 세팅한다.
   (가장 빠른 시간 안에 모든 바나나를 먹을 수 있는 k값 중 가장 작은 값이 max(piles)이기 때문이다.)
2. 바이너리 서치를 이용하여 left와 right의 범위를 좁히면서 mid 값이 문제 조건에 맞는 k값이 될 수 있으면 result에 갱신한다.
3. 더 이상 left와 right의 범위를 좁힐 수 없으면(바이너리 서치가 끝났으면) result를 리턴한다.

이 경우 시간 복잡도는 piles의 길이를 N이라고 했을 때, O(log(max(piles)) * N), 공간 복잡도는 O(1)이 된다.

 

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # left, right, result 세팅
        left = 1
        right = max(piles)
        result = right

        # 바이너리 서치 이용하여 result 갱신
        while left <= right:
            # left와 right의 중간 값
            mid = (right-left)//2 + left

            # 현재 mid의 값이 k 값일 때 모든 바나나를 먹기 위한 시간 계산 
            need_h = 0
            for pile in piles:
                need_h += math.ceil(pile/mid)
            
            if need_h > h:
                # 경비원이 돌아올 때 까지 다 못 먹으므로 갱신 x
                # 한 시간에 더 많이 먹어야하므로 left를 이동
                left = mid + 1
            else:
                # 경비원이 돌아올 때 까지 다 먹을 수 있으므로 갱신 O
                result = mid
                # 한 시간에 더 적게 먹어도 조건에 맞는지 
				# 확인하기 위해 right를 이동
                right = mid - 1
        return result

 

추가 정보

처음에 left를 1이 아닌, math.ceil(sum(piles)/h)로 하여 최적화할 수 있다고 한다. 하지만 언어에 따라서 오버플로우가 발생할 수 있고, 시간 복잡도에 큰 의미는 없는 것 같다.

 

 

 

https://leetcode.com/problems/koko-eating-bananas/

Koko Eating Bananas - LeetCode