[LeetCode#875] Koko Eating Bananas

 

❐ Description

---

문제 링크	Koko Eating Bananas
난이도	medium / Gold 4~3

 

 

 

 

 

❐ 문제 분석 및 접근

---

 

• piles : 바나나 더미
• h : 가드가 자리를 비우는 시간
• k : 원숭이가 한 시간동안 먹을 수 있는 바나나 갯수

 

int[] piles = {10, 13, 34, 55}

예를 들어 위와 같은 경우에, 원숭이가 시간당 먹을 수 있는 바나나의 갯수(k)가 15라면 

원숭이가 모든 바나나 더미를 다 먹는데 걸리는 시간은 아래와 같을 것이다.

‣ 10개 - 1시간
‣ 13개 - 1시간
‣ 34개 - 3시간
‣ 55개 - 4시간

 

 

원숭이가 먹을 수 있는 최소 바나나 갯수는 1개이고 최대 바나나 갯수는 piles 중 가장 큰 수이다.

⇨ 정답 k는 이 사이에 존재한다.

 

그리고 위의 예시에서 `k = 15` 일 때 34개의 바나나를 먹는데 3시간이 걸린다.

⇨ `15개 / 15개 / 나머지 4개`

 

이 부분을 계산하기 위해서는 올림을 구현해줘야 한다.

⇨ (pile + k - 1) / k

 

 

 

 

 

❐ Solution

---

public class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = (int) le9;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            int takenHour = 0;
           	for (int pile : piles) {
                // 올림 연산
                takenHour += (pile + mid - 1) / mid;
            }
            
            if (takenHour <= h) {
                // 현재 mid도 다음 범위에 포함되어야 한다.
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

 

 

 

 

 

---