릿코드 875. Koko Eating Bananas 바이너리 서치

 

875. Koko Eating Bananas

Koko Eating Bananas - LeetCode

수업 때 들은 내용 복습 겸 다시 풀었다. 

 

--

코코는 바나나 먹는 걸 좋아해요. n개의 바나나 더미가 있고, i번째 더미에는 [i]개의 바나나가 있습니다. 경비원은 떠났고 몇 시간 후에 다시 올 것입니다.

코코는 시간당 바나나 섭취 속도 k를 결정할 수 있습니다. 매 시간마다 그녀는 바나나 더미를 선택하고 그 더미에서 k개의 바나나를 먹습니다. 더미에 k개 미만의 바나나가 있으면 대신에 바나나를 모두 먹고 이 시간 동안 더 이상 바나나를 먹지 않습니다.

코코는 천천히 먹는 것을 좋아하지만 경비원이 돌아오기 전에 바나나를 모두 먹고 싶어합니다.

그녀가 h 시간 내에 모든 바나나를 먹을 수 있도록 최소 정수 k를 반환합니다.

 

--

 

 

수업때 받은 코드로 풀이

 

원숭이가 주인이 오기 전 h 시간동안 바나나를 먹으려고 한다. 

pile 바나나 더미  = [ 30, 11, 23, 4, 20] 

h = 5

 

원숭이가 5시간 내에 먹을 수 있는 최소 바나나 갯수 k 를 구해야한다. 

 

예를 들어 원숭이가 1시간에 20송이를 먹을 수 있다고 치자

30송이는 20송이 + 10송이이다. 그러면 이 원숭이는 "그녀는 바나나 더미를 선택하고 그 더미에서 k개의 바나나를 먹습니다. 더미에 k개 미만의 바나나가 있으면 대신에 바나나를 모두 먹고 이 시간 동안 더 이상 바나나를 먹지 않습니다."

이 조건에 의해 30송이를 먹는데 2시간이 걸리는 셈이다. 

 

그러면 1시간에 20송이를 먹는 원숭이는 

2시간 + 1시간 + 2시간 + 1시간 + 1시간 = 총 7시간이 걸린다. 5시간 내에 먹기 실패~!

 

이걸 바이너리 서치를 이용해 풀어보자

우리가 구해야할 k의 범위를 정하고 

중간값 m을 지정해 그 m으로 piles 안에 있는 바나나를 먹었을 때 h보다 크면 실패!

h보다 작거나 같으면 시간 안에 먹기 성공!!

 

left 1, right0 을 준 건 초기화를 위함

isEdible이 true면 그 중간값이 답이다

right로 리턴하는 까닭은  m 변수 선언이 로컬로 되어있어서. 

 

중간값을 구할 때 나는 보통 (left + right ) /2 로 구하는데 이번에 다른 방법을 알았다.

 

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left =1 , right =0;
     
        for (int p: piles){
            right = Math.max(right, p);
      
        }
        while(left < right){
             
            int m = left +(right -left)/2;
           
            if ( isEdible(m, piles,h)){
                right = m;
         
            } else{
                left = m + 1;
            
            }
        }
     
        return right;
    }
    private boolean isEdible(int unit, int[] piles, int h){
    
        int curHour = 0;
        for (int p: piles){
          
            curHour += p /unit + (p%unit > 0 ? 1:0);
          
            if (curHour > h){

                return false;
            }
        }
        return true;
    }
}

 

int m = left + (right - left) /2;

로 하는 이유는 오버플로우를 방지하기 위해!

만약 left와 right가 각각 int의 최대범위값을 가지고 있다면 기존 코드대로 하면 나누기 2를 하기 전에 오버플로우 현상이 발생한다.