Leetcode - Koko Eating Bananas

wanderer-s·2022년 1월 20일
0

Algorithm

목록 보기
10/19
post-thumbnail

Problem

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는 바나나 먹는것을 정말 좋아한다. n개의 바나나 더미가 있고, i번째 바나나 더미에는 piles[i]개의 바나나가 있다.
경비원들은 h시간이 지나면 돌아온다.

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는 바나나를 시간당 바나나를 먹는 속도 k를 정할 수 있다. 매 시간마다 그녀는 바나나 더미를 선택해서 k개의 바나나를 먹는다. 만약 바나나더미의 바나나 개수가 k보다 적다면, 그녀는 모든 바나나를 먹고 남은 시간동안 바나나를 더 이상 먹지 않는다

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

koko는 바나나를 천천히 먹기를 원하지만 경비원들이 돌아오기 전에 모든 바나나를 먹길 원한다. (욕심쟁이네)

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

h시간 안에 그녀가 바나나를 전부 먹을 수 있는 최소한의 정수 k를 구하시오

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 <= 1 ** 4
  • piles.length <= h <= 1 ** 9
  • 1 <= piles[i] <= 10 ** 9

Solution

JavaScript

/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
var minEatingSpeed = function(piles, h) {
    const pilesCount = piles.length
    let min = 1,
        max = Math.max(...piles),
        k = max
    if(pilesCount === h) {
      // 더미 개수와 주어진 시간이 같으면 시간 당 바나나더미 하나씩 먹었다는 의미
      // 따라서 더미중 가장 바나나가 많은 갯수가 K 가됨
        return max
    }
    
    function findTime(hourPerEat) {
      // 시간당 몇개를 먹는지 넣으면 총 시간을 찾아주는 함수
        return piles.reduce((time, banana) => {
          // 다 먹고 시간이 남아도 더 이상 먹지 않으니 Math.ceil로 올림 해주어야 함
            time += Math.ceil(banana/hourPerEat)
            return time
        }, 0)
    }
    // 이진탐색
    while(min <= max) {
        const mid = Math.floor((max + min) / 2)
        
        if(findTime(mid) <= h) {
            k = mid
            max = mid - 1
        } else {
            min = mid + 1
        }
    }
    return k
};

Feedback은 언제나 환영입니다🤗

profile
You only get one life. It's actually your duty to live it as fully as possible.

0개의 댓글