[LeetCode] 875. Koko Eating Bananas - 문제풀이

Description

주어진 배열의 각 요소는 바나나의 개수를 뜻하고 h시간안에 다 먹을 수 있는 가장 적은 수의 바나나 먹는 속도 k를 반환해 주면 됩니다.

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

Constraints:

• 1 <= piles.length <= 104
• piles.length <= h <= 109
• 1 <= piles[i] <= 109

Solution 1. 전체 탐색(brute force)

public int minEatingSpeed(int[] piles, int h) {

    //1. brute force
    int len = piles.length;
    int speed = 1;
    while (true) {
        int time = 0;
        for (int i = 0; i < len; i++) {
            time += Math.ceil((double) piles[i] / speed);
            if (time > h) { //다 못먹었는데 시간 초과됨
                break;
            }
        }
        if (time <= h) {  //시간안에 다 먹었으면 return;
            return speed;
        } else {
            speed++;
        }
    }
}

전체 탐색하는 방법입니다. 한 시간에 바나나 1개를 먹을 수 있는 것 부터 시작하여 바나나 먹는 속도를 2,3,... 으로 늘려나가며 최초 바나나를 다 먹는 케이스를 반환해 줍니다. 시간복잡도가 높아 Time Limit Exceeded 가 발생하여 다른 방법을 찾아야합니다.

• 시간 복잡도 : O(nm)
• 공간 복잡도 : O(1)

Solution 2. 이진 탐색(binary search)

public int minEatingSpeed2(int[] piles, int h) {

    //2. binary search 
    Arrays.sort(piles);
    int len = piles.length;
    int start = 1;
    int end = piles[len-1];

    while(start < end){
        int speed = (start+end) / 2;  // 중간 스피드부터 시작
        int time = 0;
        for (int i = 0; i < len; i++) {
            time += Math.ceil((double)piles[i]/speed);
            if(time > h){ //다 못먹었는데 시간 초과됨, 속도를 올려야함
                start = speed+1;
                break;
            }
        }
        if(time <= h){  //시간안에 다 먹었으면 속도를 줄여서 다시 확인
            end = speed;
        }
    }
    return start;

}

이진 탐색을 이용하여 최소 먹는 시간을 찾아 나가는 방법입니다. 가장 빠르게 먹을 수 있는 속도는 배열내의 최대값이므로 정답은 1~최대값(end) 사이입니다. 여기서 중간 속도를 계속 스캔해가며 최초로 성공하는 케이스를 찾아 나갑니다.

Reference

Koko Eating Bananas - LeetCode