[BinarySearch][Medium] 875. Koko Eating Banans

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

 

아래의 조건을 만족하는 divider를 찾아라. 

해당 divider로 각 입력된 수를 나누되 나머지가 있으면 1을 더한다.(코코가 시간이 남아도 해당 pile만 시간내에 먹는다)

그 나눈 최종 합이 hour 보다 같거나 작은(시간내에 먹어야 한다)

최소의 divider값을 찾아라. 

 

 

우선 koko가 바나나를 먹는다에 비유를 해서 문제를 제시 했으므로, 

구문들을 로직 체계로 변환을 해야 한다. 

 

그것이 위에 명기한 것이며, 

결국 조건을 만족하는 최소의 divider값을 찾는 것이 문제가 원하는 답이다. 

 

조건을 만족한다

 => divider로 나눈 총합이 hour 보다 같거나 작아야 한다. 

이 중 최소 divider 값을 찾는다

 => 조건을 만족할 때, 가장 왼쪽에 존재하는 값(최소값)을 찾는다.

 

이 divider를 binary search로 찾는다. 

 

코드 

int minEatingSpeedBS(vector<int>& piles, int left, int right, int h)
{
    // 검색 종료 - 마지막 만족값(더 큰값) left 반환.
    if (left > right)    return left;

    int mid = left + (right - left) / 2;

    // 조건 만족 checking 로직.
    long needH = 0;
    for (int q = 0; q < piles.size(); ++q)
    {
        int div = piles[q] / mid; 
        if(piles[q] - div*mid > 0)
            div += 1;
        needH += div;
    }

    if (needH <= h)	// 조건을 만족하면 최소 divider를 찾기 위해 작은 쪽으로 검색.
        return minEatingSpeedBS(piles, left, mid - 1, h);
    else            // 조건을 만족하지 않으므로, 더 큰 divider로 검색.
        return minEatingSpeedBS(piles, mid + 1, right, h);
}

int minEatingSpeed(vector<int>& piles, int h) 
{
    int maxV = 1;
    for(int q = 0; q < piles.size(); ++q)
        maxV = max(maxV, piles[q]);

    if(h == piles.size())
        return maxV;

    return minEatingSpeedBS(piles, 1, maxV, h);
}

 

 

결과