LeetCode (C/C++, Java) 1760. Minimum Limit of Balls in a Bag

https://leetcode.com/problems/minimum-limit-of-balls-in-a-bag/

---

풀이

이분탐색을 사용한다. 받을 수 있는 penalty의 범위를 start와 end로 잡아서 시행한다.

중간 값을 penalty라 가정하고, 현재 nums에 있는 값을 penalty로 만들 때 필요한 총 횟수가 주어진 maxOperations보다 적다면 penalty 값이 현재 받을 수 있는 최소 penalty 값이다.

이를 반복해서 가장 적은 penalty 값을 구해 반환한다.

---

C/C++ 코드

class Solution {
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        int start = 1, end = *max_element(nums.begin(), nums.end());

        int minPenalty = end;
        while (start <= end) {
            int penalty = start + (end - start) / 2;
            
            // 된다면 minPenalty 값을 갱신, maxPenalty값 갱신
            if (isPossible(nums, penalty, maxOperations))
                minPenalty = penalty, end = penalty - 1;
            else
                start = penalty + 1;
        }
        return minPenalty;
    }

    // maxOperations 안에 현재 penalty를 최대 penalty로 만들 수 있는지 확인
    bool isPossible(vector<int>& nums, int penalty, int maxOperations) {
        int totalOperations = 0;
        for (int n : nums) {
            int cnt = n / penalty;
            if (n % penalty == 0) cnt--;
            totalOperations += cnt;
        }
        return totalOperations <= maxOperations;
    }
};

 

Java 코드

class Solution {
    public int minimumSize(int[] nums, int maxOperations) {
        int start = 1, end = maxValue(nums);
        int minPenalty = end;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            
            if (isPossible(nums, mid, maxOperations)) {
                minPenalty = mid;
                end = mid - 1;
            }
            else
                start = mid + 1;
        }
        return minPenalty;
    }
    public int maxValue(int[] nums) {
        int maxVal = 0;
        for (int num : nums)
            maxVal = Math.max(maxVal, num);
        return maxVal;
    }
    public boolean isPossible(int[] nums, int mid, int maxOperations) {
        int totalOperations = 0;

        for (int n : nums) {
            int cnt = n / mid;
            if (n % mid == 0) cnt -= 1;

            totalOperations += cnt;
        }
        return totalOperations <= maxOperations;
    }
}