LeetCode : 2517. Maximum Tastiness of Candy Basket

 

문제)

 

price[i]는 i번째 사탕의 가격을 나타내고 양의 정수 k와 양의 정수 price 배열이 제공된다.

그 가게에서는 k개의 서로 다른 사탕이 담긴 바구니를 판매한다.

사탕 바구니의 맛은 바구니에 들어 있는 두 사탕 가격의 가장 작은 차이의 절대값 이다.

사탕 바구니의 최대 맛을 반환.

 

문제 난이도 : 중

 

소요시간 및 풀이)

이분탐색을 이용하여 풀었다.

 

소요 시간 : 33분

 

정답 코드

class Solution 
{
public:
    int maximumTastiness(vector<int>& price, int k) 
    {
        sort(price.begin(), price.end());

        auto check = [&](int target, int count = 1) -> bool
        {
            for (int i = 1, j = 0; i < price.size(); i++)
            {
                if (price[i] - price[j] >= target)
                {
                    j = i;
                    count++;
                }
            }

            return count >= k;
        };

        auto left = 0;
        auto right = (int)price.back() - price.front() + 1;

        while (left < right) 
        {
            auto mid = left + (right - left) / 2;

            if (check(mid)) 
                left = mid + 1; 
            else 
                right = mid;
        }

        return left - 1;
    }
};