[python3] 875. Koko Eating Bananas

풀이 일자: 23.03.08

난이도: [Medium]

분류: [Binary Search]

문제 내용

n개의 바나나 무더기가 존재하고 piles[i]의 의미는 i번째 무더기에 존재하는 바나나의 개수를 의미한다. 이를 지키는 가드가 h시간 후에 올 예정이며 이에 Koko는 시간당 k의 속도로 매 시간마다 하나의 무더기를 골라 바나나를 먹을 예정이다. 만약 선택한 무더기에 있는 바나나의 수가 k보다 적은 경우 해당 무더기에 남아있는 바나나만 먹게 된다.

 

이러한 와중에 Koko는 바나나를 최대한 천천히 먹되 Gaurd가 오기 전까지 모든 바나나를 먹으려고 할 때의 최소 k를 구하는 문제이다.

 

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

만약 k가 4라고 가정한다면,

[1,2,2,3] 즉 8번만에 다 먹게 되며 이러한 경우 k가 4일 때가 답일 것이다.

k가 3이라고 가정하면

[1,2,3,4] 즉 10번만에 다 먹게 되면 Guard가 오는 시간 이후에도 먹고 있어야 하기 때문에 답이 되지 못한다.

 

 

문제 해결 흐름

1. 이 문제는 최소한의 k를 구하는 문제로 간단하게 생각하면 속도를 1로 잡고 piles를 순회하면서 답을 구하면 되겠다.

→ 다만 이러한 방식은 1부터 차례대로 진행할 경우 시간이 많이 걸리기 때문에 이진탐색이 적합할 것이다.

 

2. 이진 탐색의 대상이 어떤 것이고 그 범위를 찾는 것이 필요하겠다.

→ 이진 탐색의 대상은 speed의 최소값을 찾는 것이기에 그 범위는 1~max(piles)일 것이다.

→ 사실상 max(piles)보다 속도를 더 늘리더라도 그 이후부터 걸리는 시간은 len(piles)로 일정할 것이다.

 

3. speed를 최소화하기 위해서는 최대한 guard 돌아오는 시간에 딱 맞춰서 다 먹어야 한다는 것을 떠올릴 수 있다.

 

4. 이진 탐색 내부의 left, right를 결정하는 조건에 대해 결정하자.

→ mid로 우선 piles를 순회하면서 각 piles의 바나나 수에 나누며 전체 걸리는 시간을 구하자.

→ 전체 걸리는 시간은 hours라고 하면 hours < h인 경우 시간이 너무 적게 걸리는 것으로 speed를 늦춰야 한다.

→ hours > h인 경우 시간이 너무 많이 걸리는 것이므로 speed를 올려야 한다.

 

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:

        left = 1; right = max(piles);

        while(left < right):
            mid = left + (right - left) // 2;
            hours = 0;

            for i in range(len(piles)):
                hours += ceil(piles[i] / mid);

            if hours <= h:
                right = mid;
            else:
                left = mid + 1;
        
        return left

 

Time Complexity: O(NLogM)

이진탐색을 진행하기에 max(piles)의 Log값과 내부에서 실제 걸리는 시간을 계산하기 위한 과정으로 인하여 NLogM정도의 시간복잡도를 가지게 될 것이다.

 

Space Complexity: O(1)

일반적인 변수를 제외하고 어떤 자료구조를 문제풀이에 사용하지 않았기 때문에 1의 공간복잡도를 가지게 될 것이다.

 

 

다른 해결 방식

 

해당 문제는 Binary Search를 의도해서 만들어진 문제로 시간 안에 도달할 수 있는지에 대한 함수를 추가로 작성한 것 외에는 User Solution과 차이가 없었다.

 

 

문제 링크

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

Koko Eating Bananas - LeetCode