[Java] LeetCode 875: Koko Eating Bananas

[문제 바로 가기] - Koko Eating Bananas

유형 : 이진 탐색

이번주 스터디는 이진 탐색을 주제로 진행한다. 문제 유형은 금방 파악했지만 예상치 못한 곳에서 헤매서 삽질을 꽤나 했다 -.-

💡 아이디어

이 문제는 Koko가 h 시간 안에 piles에 있는 바나나를 모두 먹어야 한다.
k개씩 먹는다고 칠때, piles에 있는 바나나 더미 당 k개씩 먹었을 경우 걸리는 시간을 합산한다.

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

예제로 설명하면, 바나나를 1개씩 먹는다면 총 걸린 시간은 3 + 6 + 7 + 11 = 27시간이 걸린다. 또한 바나나를 11개씩 먹으면 1 + 1 + 1 + 1 = 4시간이 걸리며, 3개씩 먹는다면 1 + 2 + 3 + 4 = 10시간이 걸린다.

문제에 나와있는 If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour. 뜻이 1시간에 먹을 수 있는 바나나의 양 k개가 piles의 i번째 값보다 작거나 남더라도(=k개로 나누어 떨어지지 않더라도) 해당 시간에 다음 더미의 바나나를 먹지 않는다는 뜻이다.

나도 이 부분에서 이해를 못해서 해설을 찾아보며 이해를 했다.

아무튼 h 시간 동안 바나나를 k개씩 먹을 때, 까탈스러운 Koko는 최대한 천천히 바나나를 먹고 싶으시단다. hour == h를 충족하는 k 중 가장 작은 값을 구해주면 된다!

---

풀이

첫번째 풀이 : 29ms

• Math.ceil 사용
• while문의 조건 left <= right, right = mid - 1

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;

        for (int pile : piles) right = Math.max(right, pile);

        while (left <= right) {
            int mid = left + (right - left) / 2;

            int hour = 0;
            for (int pile : piles) {
                hour += Math.ceil((double) pile / mid);
            }

            if (hour <= h) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

두번째 풀이 : 7ms

• Math.ceil 대신 (pile + mid - 1) / mid 사용
• while문 조건 left < right, right = mid

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1, right = 0;
        for (int pile : piles) right = Math.max(right, pile);

        while (left < right) {
            int mid = left + (right - left) / 2;

            int hour = 0;
            for (int pile : piles) {
                hour += (pile + mid - 1) / mid;
            }

            if (hour <= h) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}