코코는 시간당 바나나를 먹는 속도를 k라고 정하고, 한 더미를 집을 때 k개의 바나나를 먹는다. 만약에 한 바나나 더미가 k개보다 적으면 다음 바나나 더미로 넘어가지 않고 가만히 있는다.
경비가 오기 전에 모든 바나나 더미들을 먹을 수 있는 최소의 k를 구하자.
처음엔 문제 읽고 이해를 못했다.
그래서 코코가 바나나 다 먹고 싶은데 1시간에 k개 먹고,, 뭐?
어찌저찌 이해해서 그냥 생각 나는 대로 접근을 해봤다.
주어진 예제 중
piles = [3,6,7,11], h=8
이고k=4
라는 예제가 존재하길래
3+6+7+11 = 27, 27/8 = 3.xx
"그러면 k는 배열의 모든 원소를 더한 값을 h로 나눴을 때 소수점 올림수인가?"
라고 생각했지만, 아니었다.(당연함 너무 간단했음)
그래서 2, 3번째 예제를 쳐다봤다.
#2 piles = [30,11,23,4,20], h=5
→ k=30
#3 piles = [30,11,23,4,20], h=6
→ k=23
piles 길이 == h인 경우, k는 piles 내의 가장 큰 값이 된다.
why? 1시간에 한 더미만 먹기 때문에 30보다 작은 값을 선택하면, 0번째에서 2시간 이상 소모하기 때문
h가 6일 때는 1시간의 여유가 더 있기 때문에 2번째로 큰 수인 23이 답이 된다.
h를 증가시켜 가면서 손코딩을 계속 해봤는데, 도저히 모르겠다.
왜 이진탐색을 쓰라는 건지도 모르겠어서 답 봤다 흥
우선, k가 가질 수 있는 최댓값은 piles에서 가장 큰 원소이다.
그러면 piles 배열을 정렬하면 우리는 최댓값을 알아낼 수 있다.
문제에서는 k의 최솟값을 원하기 때문에 우리는 이분탐색으로 k를 찾아나갈 것이다.
백문이 불여일견
main 함수 & 전역 변수 작성
class Solution {
public static int validMaxNum;
public static int res;
...
public int minEatingSpeed(int[] piles, int h) {
Arrays.sort(piles);
validMaxNum = piles[piles.length-1];
res = validMaxNum;
findK(piles,h,1,validMaxNum);
return res;
}
}
findK 함수
public static int findK(int[]piles, int h, int start, int end){
while(start<=end){
int half = (start+end)/2;
long totalHour = eatBanana(piles, half);
if(totalHour > h){
start =half+1;
}
else{
res = Math.min(res,half);
end= half-1;
}
}
return res;
}
totalHour
: half개로 모든 바나나를 먹는 데 걸리는 시간eatBanana 함수
를 호출한다.eatBanana 함수
public static long eatBanana(int[] piles, int k){
long totalHour = 0;
int c =0;
for(int bananas: piles){
c = bananas%k > 0?1:0;
totalHour =bananas/k+totalHour+c;
}
return totalHour;
}
piles 배열을 순회 하면서 해당 더미의 바나나 개수를 k로 나눈 값을 totalHour에 저장한다.
만일 나머지가 존재하는 경우 +1 을 추가한다.
ex) banana = 7, k=3인 경우
7 / 3 = 2, 7 % 3 =1 이므로 totalHour은 총 3시간이 됨.
import java.util.*;
class Solution {
public static int validMaxNum;
public static int res;
public static long eatBanana(int[] piles, int k){
long totalHour = 0;
int c =0;
for(int bananas: piles){
c = bananas%k > 0?1:0;
totalHour =bananas/k+totalHour+c;
}
return totalHour;
}
public static int findK(int[]piles, int h, int start, int end){
while(start<=end){
int half = (start+end)/2;
long totalHour = eatBanana(piles, half);
if(totalHour > h){
start =half+1;
}
else{
res = Math.min(res,half);
end= half-1;
}
}
return res;
}
public int minEatingSpeed(int[] piles, int h) {
Arrays.sort(piles);
validMaxNum = piles[piles.length-1];
res = validMaxNum;
findK(piles,h,1,validMaxNum);
return res;
}
}
코코 바나나 다 뜯고 싶었지만, 그래도 해설을 보니깐 괜찮아졌다.
항상 풀이를 보면 내가 왜 이런 생각을 못했을까 자책하는 것 같다.
그렇다고 백날천날 고민해봤자 시간만 아까운 걸 알기에 빠르게 답을 보는 게 나은 선택이다.
어차피 답지 볼 거 빨리 보고 이해하자~!@~!