[LeetCode-자바] N_875 Koko Eating Bananas

0woy·2024년 7월 21일

Java bs leetcode

코딩테스트

목록 보기

27/40

📜 문제

n개의 바나나 더미가 있다.
i번째 바나나 더미는 piles[i]개의 바나나를 가지고 있다
경비는 h시간 후에 돌아온다.

코코는 시간당 바나나를 먹는 속도를 k라고 정하고, 한 더미를 집을 때 k개의 바나나를 먹는다. 만약에 한 바나나 더미가 k개보다 적으면 다음 바나나 더미로 넘어가지 않고 가만히 있는다.

경비가 오기 전에 모든 바나나 더미들을 먹을 수 있는 최소의 k를 구하자.

0. 코코 바나나 뺏기 접근

처음엔 문제 읽고 이해를 못했다.
그래서 코코가 바나나 다 먹고 싶은데 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;
    }
}

piles 배열 오름차순 정렬
validMaxNum (가능한 최댓값)에 piles의 가장 큰 원소를 저장
findK 함수를 호출하여 적절한 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개로 모든 바나나를 먹는 데 걸리는 시간

start가 end 보다 큰 경우, 적절한 경우를 모두 탐색했으므로 현재 res값을 반환한다.
중간 개수인 half를 구하고, eatBanana 함수를 호출한다.
만일 totalHour 가 주어진 hour보다 큰 경우 k는 half 보다 더 커야 하므로 start+1하여 큰 값으로 재탐색 한다.
totalHour가 hour보다 작은 경우, res에 현재 res와 half 중 작은 값을 저장하고,
end-1하여 더 작은 값으로 재탐색 한다.

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;
    }

k: 시간 당 먹을 수 있는 바나나 개수 (이전 half)

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;
    }
}