Leetcode 2064. Minimized Maximum of Products Distributed to Any Store

Alpha, Orderly·2024년 11월 14일

leetcode

목록 보기

126/140

문제

You are given an integer n indicating there are n specialty retail stores. 
There are m product types of varying amounts, 
which are given as a 0-indexed integer array quantities, 
where quantities[i] represents the number of products of the ith product type.

You need to distribute all products to the retail stores following these rules:

A store can only be given at most one product type but can be given any amount of it.
After distribution, 
each store will have been given some number of products (possibly 0). 
Let x represent the maximum number of products given to any store. You want x to be as small as possible, i.e., you want to minimize the maximum number of products that are given to any store.
Return the minimum possible x.

n개의 가게에 m개 ( 배열의 길이 ) 가지 물품을 납품한다고 가정한다.
배열은 i 종류의 물품의 갯수를 의미한다.
납품에는 아래 규칙을 따른다.
- 한 가게에는 단 한종류의 물품만 납품 가능하다.
- 납품되는 양에는 제한이 없다 ( 0개도 가능 )
모든 물품을 최대한 고르게 납품했을때 최대한 많이 받는 상점이 납품받은 갯수를 리턴하시오
- 남는 물품이 있어선 안된다.

예시

n = 7, quantities = [15,10,10]

3개의 가게에 0번 제품을 5개씩 ( 15 )
2개의 가게에 1번 제품을 5개씩 ( 10 )
2개의 가게에 2번 제품을 5개씩 ( 10 )
가장 많이 받은 가게는 5개를 받았기에 5를 리턴

제한

$m == quantities.length$
$1 <= m <= n <= 10^5$
$1 <= quantities[i] <= 10^5$

풀이

class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        least = 1
        maxima = max(quantities)

        def check(maxima: intern):
            count = 0
            for quantity in quantities:
                count += math.ceil(quantity / maxima)
            return count <= n

        while least < maxima:
            mid = (least + maxima) // 2
            chk = check(mid)
            if chk:
                maxima = mid
            else:
                least = mid + 1

        return least

여기서 답의 범위는 1개 ~ 한가지 종류의 물품의 최대 갯수가 될 것이다.

또한 우리는 범위 내 특정 값을 통해 하나를 알아볼수 있는데