Koko Eating Bananas - LeetCode
Can you solve this real interview question? Koko Eating Bananas - 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 sp
leetcode.com
수업 때 들은 내용 복습 겸 다시 풀었다.
--
코코는 바나나 먹는 걸 좋아해요. 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를 하기 전에 오버플로우 현상이 발생한다.