[LeetCode] 2064 Minimized Maximum of Products Distributed to Any Store - 매개변수탐색

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

🍊해결방법

• 주어진 quantities 배열의 숫자를 나누어 저장하는데 총 개수가 n개이면서 그 때의 최대값이 최소가 되는 걸 구하여라
• 정답을 기준으로 찾아보자
• 1 ~ 100000 안에 정답이 있다 이진탐색을 활용해 mid 값
• quantities에 숫자를 mid값으로 나눠 몇개가 만들어지는지 판단
• 여기서 주의해야할게 완전히 안 나눠떨어지면 개수를 +1 해줘야한다
• 예를들어 11을 4로 나누면 4 4 3 으로 저장이 되므로
• 만약 총 개수가 n 보다 작다면 mid값의 오른쪽은 볼 필요 없음

😀풀이

import java.util.*;

class Solution {
    public int minimizedMaximum(int n, int[] quantities) {

        // 매개변수탐색을 통해서 확인해보자

        int s = 1;
        int e = 100000;

        int ans = 0;
        while(s <= e){

            int mid = (s+e)/2;

            int cnt = 0;

            for(int i=0; i<quantities.length; i++){

                cnt += (quantities[i] / mid);
                
                // mid값으로 다 안 나눠지므로 남은 길이만큼 저장해야함
                if(quantities[i]%mid != 0)
                    cnt++;
            }

            if(cnt <= n){
                ans = mid;
                e = mid - 1;
            }
            else{
                s = mid + 1;
            }
        }

        return ans;
        
    }
}