Koko Eating Bananas

https://leetcode.com/problems/koko-eating-bananas/description/

Koko Eating Bananas - LeetCode

 

각 배열의 값을 바나나의 개수라고 할 때, 한 인덱스를 먹을 때 임의의 속도로 먹을 때 주어진 시간 내에 다 먹기 위해 필요한 최소 시간을 구하는 문제이다.

 

특이 사항으로는 인덱스를 전부 다 완료하더라도 시간 단위가 끝날 때 까지는 다음 인덱스를 먹지 못한다는 것이다. 이 부분은 나머지의 존재 여부에 따라 시간 계산을 변경하여 해결해 줄 수 있다. 그리고 이 문제의 최소 시간을 구하기 위해서는 이진 탐색을 사용하는 것이 좋다. 최소~, 최대~ 이런 형태의 문제는 이진 탐색 문제일 가능성이 크다. 정답이 될 수 있는 값이 특정 범위일 때 이 범위의 최대 값, 최소 값을 찾기 위해 좋은 알고리즘 이기 때문이다.

 

이와 같은 부분을 감안하고 문제를 풀면 풀 수 있지만, 하나의 테스트 케이스에서 걸렸었다. 총 시간의 합계를 구하는 부분에서 오버플로우가 발생했다. 이를 해결하기 위해 합계가 아니라 차이를 이용하는 방법을 사용했다. 하지만 이 차이를 이용하는 부분도 오버플로우가 발생할 수 있을 것 같다. 따라서 long타입을 사용하는 것이 더 좋았을 것 같다. 아래는 시간 계산을 위해서 차이(뺄셈)을 이용해서 문제에 통과한 코드이다.

public class Solution {  
    public int minEatingSpeed(int[] piles, int h) {  
        int low = 1;  
        int high = Integer.MIN_VALUE;  
        for (int i = 0; i < piles.length; i++) {  
            high = Math.max(piles[i], high);  
        }  
  
        int mid = 0;  
        int k = Integer.MAX_VALUE;  
  
        while (low <= high) {  
            mid = low + (high - low) / 2;  
            // int time = 0;  
            int time = h;  
            for (int i = 0; i < piles.length; i++) {  
                int pile = piles[i];  
                // time += pile % mid == 0 ? pile / mid : pile / mid + 1;  // [805306368,805306368,805306368] overflow  
                time -= pile % mid == 0 ? pile / mid : pile / mid + 1;  
            }  
  
            // if(time <= h){  
            if (time >= 0) {  
                high = mid - 1;  
                k = Math.min(k, mid);  
            } else {  
                low = mid + 1;  
            }  
        }  
  
        return k;  
    }  
}