문제 링크

내 코드

해설 참고.

Solution

Approach: Binary Search on The Answer

• 39ms, 59.78MB
• Complexity
  • Let $k$ be the maximum value in the nums array.
  • Time Complexity: $O(n \log k)$
  • Space Complexity: $O(1)$

class Solution {
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        // Binary search bounds
        int left = 1;
        int right = 0;

        for (auto num : nums) {
            right = max(right, num);
        }

        // Perform binary search to find the optimal maxBallsInBag
        while (left < right) {
            int middle = (left + right) / 2;

            // Check if a valid distribution is possible with the current middle
            // value
            if (isPossible(middle, nums, maxOperations)) {
                right = middle;  // If possible, try a smaller value (shift
                                 // right to middle)
            } else {
                left = middle + 1;  // If not possible, try a larger value
                                    // (shift left to middle + 1)
            }
        }

        // Return the smallest possible value for maxBallsInBag
        return left;
    }

private:
    // Helper function to check if a distribution is possible for a given
    // maxBallsInBag
    bool isPossible(int maxBallsInBag, vector<int>& nums, int maxOperations) {
        int totalOperations = 0;

        // Iterate through each bag in the array
        for (int num : nums) {
            // Calculate the number of operations needed to split this bag
            int operations = ceil(num / (double)maxBallsInBag) - 1;
            totalOperations += operations;

            // Total operations exceed maxOperations, return false
            if (totalOperations > maxOperations) return false;
        }

        // We can split the balls within the allowed operations, return true
        return true;
    }
};

GPT - Solution 코드 추가 설명

아래 코드는 앞서 설명한 알고리즘 아이디어를 C++ 코드로 구현한 예시입니다. 전반적인 로직은 다음과 같습니다:

1. 이진 탐색 범위 설정

   • left = 1: 가장 최소한으로 가능한 최대 공 개수(이론상으로 모든 공을 다 쪼개어, 각 주머니에 공이 1개씩만 들어가게 할 수도 있다고 가정).
   • right = 0: 초기값을 0으로 놓고, nums 배열을 순회하면서 가장 많은 공을 가진 주머니의 공 개수를 right로 설정합니다. 이 값은 최대 한계값이 될 수 있습니다(더 줄일 수 없는 상한).

   이렇게 하면 최대 공 개수(x)의 탐색 범위가 [1, 가장 큰 주머니의 공 개수]가 됩니다.

2. 이진 탐색 루프
   while (left < right)인 동안 다음을 반복:

   • middle = (left + right) / 2 로 중간값을 구합니다. 이 값은 현재 가정하는 “주머니당 공의 허용 최대 수”입니다.
   • isPossible(middle, nums, maxOperations) 함수를 호출하여, 모든 주머니의 공 수를 middle 이하로 만드는 데 필요한 연산 횟수가 maxOperations 이하인지 확인합니다.
     • 만약 true라면(가능하다면), right = middle로 설정해 더 작은 값으로도 가능한지(더 까다롭게 만들 수 있는지) 시도합니다. 즉, 최대 공 개수를 줄여볼 수 있습니다.
     • 만약 false라면(가능하지 않다면), left = middle + 1로 설정하여 middle보다 더 큰 값으로 허용치를 늘려줍니다. 즉, 너무 빡빡한 기준이므로 기준을 완화합니다.

   이 과정을 통해 가능한 최소의 maxBallsInBag 값을 탐색합니다.

3. isPossible 함수
   isPossible(int maxBallsInBag, vector<int>& nums, int maxOperations):

   • maxBallsInBag는 현재 가정하는 “한 주머니 당 허용하는 최대 공 개수”입니다.
   • nums는 각 주머니에 들어있는 공의 수를 나타내는 벡터이고, maxOperations는 허용 가능한 최대 연산 횟수입니다.

   동작 과정:

   • totalOperations = 0으로 초기화합니다.
   • 각 주머니 num에 대해:
     • 이 주머니를 최대 maxBallsInBag 이하로 만들기 위해 필요한 나누기 연산 횟수를 계산합니다.
     • 연산 횟수 계산 방법:
       (ceil(num / (double)maxBallsInBag) - 1)
       예를 들어, num = 9, maxBallsInBag = 3이라면
       ceil(9/3) = 3개의 주머니로 나누어야 하므로 연산 횟수는 3 - 1 = 2번입니다.
       (원래 하나의 주머니를 3개로 나누려면 2번 나누기 연산이 필요)
     • 이 값을 totalOperations에 누적합니다.
     • 만약 totalOperations가 maxOperations를 초과하면, 이 분배는 불가능하므로 false를 반환합니다.

   모든 주머니에 대해 검사한 후에도 totalOperations <= maxOperations이면, 이 설정으로도 모든 주머니 공 수를 maxBallsInBag 이하로 만들 수 있음을 의미하므로 true를 반환합니다.

정리:

• minimumSize 함수는 이진 탐색을 통해 가능한 최소의 maxBallsInBag 값을 찾습니다.
• isPossible 함수는 주어진 maxBallsInBag로 각 주머니를 나눴을 때 연산 횟수가 제한 내에 들어가는지 검사합니다.
• 결국 최소한의 “최대 공 개수”를 찾아내는 로직입니다.