leetcode 875) Koko Eating Bananas

LV. Medium 🧐

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

Koko Eating Bananas - LeetCode

 

문제

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 speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

 

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23

 

Constraints:

• 1 <= piles.length <= 10^4
• piles.length <= h <= 10^9
• 1 <= piles[i] <= 10^9

 

문제 해결법

처음에는 그냥 1부터 쭉 찾는 방법으로 풀었더니 역시나 타임 엑시드..ㅋㅋㅋㅋ

 

binary search로 min 값과 max 값을 사용하여 middle 값을 찾아 문제를 풀었다.

max_element 함수를 통해 백터의 맥스 값을 찾아줬다.

 

left(= min) ~ right(= right)의 중간값이 middle를 찾아 middle로 구한 시간이 h보다 크면 바나나를 더 먹어야 되니깐 left = middle + 1로 옮겨줬다.

왜 +middle이 아니고 + (middle + 1)이냐면 h랑 비교할 때 초과로 체크해줬기 때문!

middle로 구한 시간이 h 이하면 바나나를 적게 먹어야 되니깐 right = middle로 바꿔준다

계속 범위를 바꾸다가 left가 right를 넘게 되면 right가 정답이다.

 

해결 코드

class Solution {
public:
	int minEatingSpeed(vector<int>& piles, int h) {
		int left = 1;
		int right = *max_element(piles.begin(), piles.end());
		int middle;

		while (left < right) {
			middle = (right + left) / 2;
			int temp = 0;
			for (int pile : piles) {
				temp += pile / middle + (pile % middle == 0 ? 0 : 1);
				if (temp > h)
					break ;
			}
			if (temp > h)
				left = middle + 1;
			else 
				right = middle;
		}
		return right;
	}
};