[리트코드] 2064

작성일: 2024-11-14

플랫폼 : https://leetcode.com/

문제 링크 : https://leetcode.com/problems/minimized-maximum-of-products-distributed-to-any-store

접근 방식

최솟값은 한 개씩 담을 수 있고, 최댓값은 quantities 배열내의 최댓값을 담을 수 있다.

따라서 최솟값과 최댓값의 중간부터 값을 시작해서, 몇 개 담을 수 있는지를 파악하고
만약, n보다 크다면 최솟값을 올리고, 작거나 같다면 최댓값을 내린다.

결과

소스 코드

import java.util.*;
class Solution {
    public int minimizedMaximum(int n, int[] quantities) {
        int left = 1;
        int right = Arrays.stream(quantities).max().getAsInt();
        int result = right;
        while(left<=right){
            int mid = (left+right)/2; // 중간점
            int cnt = 0;
            for(int q:quantities){
                cnt+= q%mid==0 ? q/mid : q/mid+1;
            }
            if(cnt<=n){
                result = mid;
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return result;
    }
}

느낀 점

완전탐색은 웬만하면 지양하고, 최대 혹은 최솟값을 구해야 할 경우에는 이분탐색을 이용하자.