[LeetCode 해석 및 풀이] 875. Koko Eating Bananas

LeetCode 문제 해석 및 풀이 방법

 

문제 875. 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.

 

한글

코코는 바나나 먹는 것을 좋아합니다. n개의 바나나 더미가 있고, i번째 더미에는 piles[i]개의 바나나가 있습니다. 경비는 나간뒤 h시간 뒤에 돌아옵니다.

 

코코는 바나나/시간 속도 k를 정할 수 있습니다. 각 시간마다 그녀는 무슨 더미의 바나나를 먹을지 결정하고 해당 더미에서 k개의 바나나를 먹습니다. 만약 해당 더미에 k개보다 적은 바나나가 있다면, 그녀는 다 먹고 더 이상 다른 바나나를 해당 시간에 먹지 않습니다.

 

코코는 느리게 먹는 것을 좋아하나 경비가 돌아오기 전까지 모든 바나나를 먹고 싶어합니다.

 

그녀가 h시간 내에 모든 바나나를 먹을 수 있는 최소 정수 k를 반환하시오.

 

제한조건

• 1 <= piles.length <= 10^4
• piles.length <= h <= 10^9
• 1 <= piles[i] <= 10^9

 

입출력 예

입력	출력
piles = [3,6,7,11], h = 8	4
piles = [30,11,23,4,20], h = 5	30
piles = [30,11,23,4,20], h = 6	23

 

 

해답 및 해설

파이썬 (Python)

첫 번째 풀이 (좋지 않음)

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def eating_time(k:int) -> int:
            # if k == 0: return float("inf")
            return sum((b+k-1)//k for b in piles)

        left = 1
        right = max(piles)

        while left <= right:
            mid = (left + right) //2
            
            if eating_time(mid) == h and (mid == 1 or eating_time(mid-1) > h):
                return mid
            elif eating_time(mid) <= h:
                right = mid -1
            else:
                left = mid + 1
        
        if eating_time(mid) > h:
            return mid + 1
        else: return mid

첫 번째 푼 풀이로, 그리 좋지는 못한 풀이다. 아래와 같은 아이디어로 풀었다.

• neetcode 로드맵에 나온대로 이진 탐색을 이용해서 바나나 먹는 속도를 구해주었다. 만약 해당 내용이 없었다면 떠올리지 못 했을 수도...
• 바나나를 먹는 최소 속도는 1, 최대 속도는 가장 많은 바나나 더미로 하였다.
• k 최소값을 구하기 위해 k는 만족하나 k-1은 만족하지 않은 값을 구하려 하였다. 하지만 아래에서 보겠지만 해당 과정은 쓸모없고 오히려 속도를 낮추는 원인이었다.

 

두 번째 풀이 (보통)

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def eating_time(k:int) -> int:
            return sum(ceil(b/k) for b in piles)

        left = 1
        right = max(piles)

        while left <= right:
            mid = (left + right) //2

            if eating_time(mid) <= h:
                right = mid -1
            else:
                left = mid + 1
        
        return left

속도가 늦게 나오자 보통 다른 사람들의 풀이를 보고 개선한 풀이

• 단순히 먹는 시간이 작거나 같을 때만 우측 인덱스를 바꾸게 만들어 쓸대없는 과정 없이 답에 다가갈 수 있게 되었다.
• 최소값을 구하는 것은 left값을 리턴하는 것으로 해결. left값은 시간이 h보다 클 때만 하나 더 큰 값으로 바뀌기 때문에 가장 최소의 k값을 구할 수 있게 해준다.
• (b+k-1)//k 부분을 그냥 ceil(b/k)로 바꿈

 

세 번째 풀이 (좋음)

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def eating_time(k:int) -> int:
            return sum(ceil(b/k) for b in piles)
        sum_all = max_val = 0
        pile_n = len(piles)

        for x in piles:
            sum_all += x
            if x>max_val: max_val = x

        left = ceil(sum_all/h)
        right = min(ceil((sum_all-pile_n+1)/(h-pile_n+1)), max_val)

        while left <= right:
            mid = (left + right) //2

            if eating_time(mid) <= h:
                right = mid -1
            else:
                left = mid + 1
        
        return left

이진 탐색의 범위를 축소시켜 시간을 단축한 풀이.

• 최소값은 전체 바나나 수를 시간으로 나눈 값으로 이상적으로 딱 떨어지도록 균일하게 분배되어 있을 때의 최소값 상황.
• 최대값은 한 더미에 (전체 바나나) - ((더미 갯수) -1)개가 몰려있고, 나머지 (더미 갯수) -1개의 더미에는 1개씩 있는 상황. 이 때 1개씩만 먹는 것을 강요받으므로 나머지 더미에서 더 빠른 속도로 바나나를 먹어야 된다. 이럴 경우 가장 많은 더미를 먹는데 소비하는 시간이 (전체 시간) - ((더미 갯수) - 1)이 된다. 그래서 값이 저렇게 나온다.