[NeetCode-LeetCode] Koko Eating Bananas Java

반응형

728x90

[NeetCode-LeetCode] Koko Eating Bananas - Medium

---

접근

• 이진 탐색 

---

풀이

바나나 개수가 담긴 배열이 주어지고 시간이 주어질 때 모든 바나나를 다 먹는데 걸리는 최소 시간당 바나나 개수를 구해야 한다. 코코는 한 시간의 k개만큼 바나나를 먹을 수 있는데 모든 바나나를 제한 시간 안에 먹어야 할 때 시간당 먹어야 하는 바나나의 개수인 k의 최솟값을 구하는 문제이다. 

 

바나나 더미의 최대 개수가 매우 큰 값이기 때문에 이진 탐색을 통해 구해주었다.

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

        while (left < right) {
            int mid = (right + left) / 2;
            if (checkEatAll(piles, h, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

더미의 최소 개수는 1이고 최대 개수는 10의 9 제곱의 값으로 이진 탐색을 위한 각 포인터의 초기값으로 설정한다. 두 포인터가 같아지는 구간이 최솟값이 되는 지점으로 시간당 중간 값의 바나나를 먹는 경우 제한 시간 내에 모든 바나나를 다 먹을 수 있는지 검사하고 가능하다면 오른쪽 포인터인 시간당 바나나 개수를 줄여 더 작은 값 탐색이 가능한지 확인하고 불가능하다면 왼쪽 포인터인 시간당 바나나 개수를 늘려 제한 시간 내에 바나나를 다 먹을 수 있게 만들어준다. 

    private boolean checkEatAll(int[] piles, int h, int k) {
        int hours = 0;
        for (int pile : piles) {
            hours += (pile - 1) / k + 1;
            if (hours > h) return false;
        }
        return true;
    }

바나나를 다 먹을 수 있는지 검사하는 함수로 시간당 k 개의 바나나를 제한 시간 내에 다 먹을 수 있는지 체크한다. 걸리는 시간을 구하는 부분은 

hours += (pile - 1) / k + 1;

이 부분으로

hours += pile/k;

if(pile % k > 0) hours++;

바나나 개수를 나눈값과 나머지가 있다면 올림 처리를 하는 코드와 동일한 코드이다. 미리 나눌 값에 -1을 하여 나눈 뒤 나머지와 상관없이 +1을 시켜주면 동일한 결과를 얻을 수 있다.

---

전체 코드

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

        while (left < right) {
            int mid = (right + left) / 2;
            if (checkEatAll(piles, h, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private boolean checkEatAll(int[] piles, int h, int k) {
        int hours = 0;
        for (int pile : piles) {
            hours += (pile - 1) / k + 1;
            if (hours > h) return false;
        }
        return true;
    }
}