2064. Minimized Maximum of Products Distributed to Any Store

2064. Minimized Maximum of Products Distributed to Any Store
Solved
Medium
Topics
Companies
Hint
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 개의 상점에 판매 가능한 물품 ( quantities ) 의 최대 갯수를 계산하는 내용입니다.

주어진 quantities 의 종류마다 상점 하나를 점유해야 하므로 가장 큰 갯수의 물품을 사용하기 위해서는 공평한 배분이 이뤄져야 합니다.

물품의 종류의 구분이 필요하므로 물품의 총합에서 N 을 나눌 수는 없고

가장 큰 갯수 X 를 기준으로 물품 종류가 모두 배분이 가능한 지 판별해야 합니다.

예를 들어 X=3 인 경우 물품의 총 갯수를 나누어 올림 ( 상점에 모두 넣어야 하므로 ) 의 값의 물품 종류의 모든 합이 상점 갯수 N 을 넘어서지 않으면 성공합니다.

이 과정에서 몰품을 모두 확인하는데 O ( N ) 이 소요됩니다.

그리고 배분 가능한 X 의 순회를 O ( N ) 를 사용하면 총 O ( N ^ 2 ) 로 시간 초과가 발생합니다.

 

이러한 문제에서 O ( N ) 을 줄이는 방법은 Binary Search 를 사용하여 O ( logN ) 을 사용하는 겁니다.

X 의 min, max 는 문제에서 제공하는 숫자 범위에 존재하므로 mid 값을 옮겨가며 가장 큰 X 값을 찾습니다.

 

단, Binary Search 로 X 를 찾은 경우에는 바로 사용하지 않고 더 작은 X  가 존재할 수 있으므로 추가로 Binary Search 를 수행합니다.