LC 875. Koko Eating Bananas

Koko Eating Bananas

• 약간 어려워진 이진탐색 문제
• 문제 이해가 잘 안되었음.

문제 설명

• 바나나 개수 배열(piles)과 시간(h)이 주어진다.
• koko가 원숭이를 먹을 때 주어진 시간 안에 바나나를 다 먹는 최소 스피드(k)를 구하는 문제이다.

테스트 케이스를 통해 이해를 좀 더 해보자.

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

• koko는 8시간 안에 모든 바나나를 먹어야 한다.

• 바나나 더미(pile)당 먹을 수 있는 스피드(k)를 구해야 한다.

• 만약 koko가 가장 천천히 먹는다고 할 때의 경우
  더미 당 k=1일 때이고 가장 빨리 먹는다면 piles에서 가장 큰 수인 11이 된다.

  • 즉 가장 천천히 먹을 때 전체 시간 계산 => 3/1 + 6/1 + 7/1 + 11/1 = 27이 된다.

  • 가장 빨리 먹는다면, 3/11 + 6/11 + 7/11 + 11/11 = 4이다.
    (더미를 다 먹어야하기 때문에 남는 소수점이 생기면 올림을 해야 한다.)

• 결국 최소 k 값을 찾는 이진탐색 문제라는 걸 알게 된다.

• k = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]이 될 수 있다.

주의해야 할 점

k가 4, 5, 6일 때 전체 시간을 계산해보면 h인 8이 나온다.
(평범한 이진탐색에서 조금 어렵게 만든 조건)
문제에서 koko가 가장 천천히 먹을 때를 구하라고 했으므로
이중 제일 작은 k인 4를 반환해야 한다!

전체 시간을 계산할 때, 값을 저장해 놓고 최소값을 그때 그때 갱신해 주는 식으로 해결할 수 있다.

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # k의 값의 범위
        left, right = 1, max(piles)
        # 전체시간 값을 일단 가장큰 right로 초기화(for 최소값)
        res = right
        
        while left <= right:
            k = (left + right) // 2
            totalHour = 0
            for pile in piles:
                totalHour += math.ceil(pile / k)
            
            # 최대 값이 같거나 작은 경우, res 값을 갱신
            if totalHour <= h:
                res = min(res, k)
                right = k - 1
            else:
                left = k + 1
                
        return res

시간복잡도: O(log(max(n)) * n)

• piles 최대값 구하는 경우, 반복문 돌며 이진탐색을 적용함.