Leetcode 1760. Minimum Limit of Balls in a Bag

문제

You are given an integer array nums where the ith bag contains nums[i] balls. You are also given an integer maxOperations.

You can perform the following operation at most maxOperations times:

Take any bag of balls and divide it into two new bags with a positive number of balls.
For example, a bag of 5 balls can become two new bags of 1 and 4 balls, 
or two new bags of 2 and 3 balls.
Your penalty is the maximum number of balls in a bag. 
You want to minimize your penalty after the operations.

Return the minimum possible penalty after performing the operations

• 여러개의 공이 들어있는 백이 주어집니다. 배열은 i번째 백의 공의 갯수를 의미합니다.
• 한번의 연산에 당신은 한개의 백에 있는 공들을 두개의 백에 나눠담을수 있습니다.
• 연산을 할수 있는 최대 횟수가 주어질때, 모든 연산이 끝나고 난 뒤 백에 들어있는 공의 갯수중 최댓값을 제일 작게 만들때, 그 값을 구하시오

예시

[9]

• 1번 3, 6으로 나눔
  • [3, 6]
• 1번 3, 3, 3 으로 나눔
  • [3, 3, 3]
• 최댓값은 3

제한

• $1 <= nums.length <= 10^5$
• $1 <= maxOperations, nums[i] <= 10^9$

풀이법

• 가능한 최댓값의 범위를 정한 뒤, 이를 이진탐색으로 확인한다.
• 가능하면 기록해두다가 리턴

class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        l = 1
        r = max(nums)

        ans = r

        while l <= r:
            mid = (l + r) // 2
            count = 0
            
            # mid 가 분리 후 최댓값일 경우 몇번 분리 해야 하는지 확인
            for num in nums:
                count += ceil(num / mid) - 1

			# 엥 분리 횟수가 너무 많이 필요 -> 반려
            if count > maxOperations:
                l = mid + 1
            # 분리횟수가 딱 적당함
            # 일단 기록해 두고 더 줄여보자!
            else:
                ans = mid
                r = mid - 1

        return ans