[코테연습] 2064. Minimized Maximum of Products Distributed to Any Store

배열 / 이진탐색 문제

https://leetcode.com/problems/minimized-maximum-of-products-distributed-to-any-store/description/?envType=daily-question&envId=2024-11-14

문제분석

• 목표: n개의 매장에 quantities 배열에 있는 제품을 나누어 각 매장이 받는 최대 제품 수를 최소화하는 것입니다.
• 제약사항:
  • 각 매장은 quantities 배열에 포함된 여러 제품 중 일부를 가져가야 하며, 모든 매장이 받는 제품 수의 최대값을 최소로 유지해야 합니다.
  • 모든 quantities의 요소를 배분할 수 있을 만큼의 충분한 매장(n)이 주어진다고 가정합니다.
• 예시 이해:
  • quantities = [7, 4, 5], n = 3일 때:
    • 한 매장에 3개씩 분배하면 충분히 n개의 매장에 나눌 수 있습니다.
    • 각 매장에 3개 이하로 분배 가능할 경우, 최대값은 3으로 최소화됩니다.

문제풀이

1. 이분 탐색 설정:
   • 매장에 분배할 제품 수의 최소값 min을 1로, 최대값 max를 quantities 중 가장 큰 값으로 설정합니다.
2. 이분 탐색 진행:
   • mid = (min + max) / 2로 중간값을 계산하여, 이 값을 각 매장에 최대 배분 가능한 제품 수로 가정합니다.
   • 각 quantity를 mid로 나누어 필요한 매장 수를 계산합니다.
     • 필요한 매장 수 = store += (quantity + mid - 1) / mid (정수 올림 연산)
   • 필요한 매장 수가 n 이하라면, max를 줄여 더 작은 최대값을 찾도록 탐색 범위를 좁힙니다.
   • 필요한 매장 수가 n보다 크면 min을 늘려 더 큰 최대값을 탐색합니다.
3. 최종 반환값:
   • 이분 탐색이 끝날 때 min에 최적의 최대값이 저장됩니다.

 

> java

 

class Solution {
    public int minimizedMaximum(int n, int[] quantities) {
        int[] copiedArr = Arrays.copyOf(quantities, quantities.length);
        Arrays.sort(copiedArr);
        int min = 1;
        int max = copiedArr[copiedArr.length-1];

        while(min < max) {
            int mid = (max + min) / 2;
            int store = 0;
            for (int i = 0; i < quantities.length; i++) {
                int q = quantities[i];
                // 나눈 값을 올림한 것과 동일한 효과
                store += (q + mid - 1) / mid;
               
            }
            if (store > n) {
                min = mid+1;
            } else {
                max=mid;
            }
        }
        return min;
    }
}

 

 

> python

 

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

        while min_val < max_val :
            mid = (min_val+max_val) // 2

            store = 0
            for q in quantities :
                store += (q + mid - 1) // mid
            if store > n :
                min_val = mid+1
            else :
                max_val = mid
        return min_val