[Leetcode] 1760. Minimum Limit of Balls in a Bag

문제 요약

• 알고리즘 분류:   이분탐색, 이진 탐색
• 난이도: Medium
• 문제내용:
  • 가방마다 공이 들어 있고, 우리는 특정 횟수만큼 가방을 나눌 수 있습니다.
  • 한 가방을 두 개로 나눌 때 각 가방에는 반드시 1개 이상 공이 있어야 한다.
  • 작업을 수행한 후 가능한 최소 패널티를 반환하세요.
• 사이트 주소: https://leetcode.com/problems/minimum-limit-of-balls-in-a-bag/

문제풀이

 이번 문제에는 이분탐색을 활용한 문제이다. 관련 내용은 밑에 글에서 확인 해보면 된다.

https://jih3508.tistory.com/288

[알고리즘 이론] 이진 탐색(Binary Search)

문제의 핵심:

• 가방을 둘로 나누는 연산을 최대 maxOperations번까지 할 수 있습니다
• 목표는 "가장 많은 공이 들어있는 가방"의 공 개수를 최소화하는 것입니다

📝 예시로 이해해보기

예시 1: nums = [9], maxOperations = 2

초기 상태: [9]
1번 나누기: [9] → [6, 3]
2번 나누기: [6, 3] → [3, 3, 3]
결과: 최대 공 개수 = 3

예시 2: nums = [2,4,8,2], maxOperations = 4

초기 상태: [2, 4, 8, 2]
1번: [2, 4, 8, 2] → [2, 4, 4, 4, 2]  (8을 4+4로 나누기)
2번: [2, 4, 4, 4, 2] → [2, 2, 2, 4, 4, 2]  (4를 2+2로 나누기)
3번: [2, 2, 2, 4, 4, 2] → [2, 2, 2, 2, 2, 4, 2]
4번: [2, 2, 2, 2, 2, 4, 2] → [2, 2, 2, 2, 2, 2, 2, 2]
결과: 최대 공 개수 = 2

💡 해결 아이디어: 이진 탐색

이 문제는 "최소값의 최대값" 문제입니다. 이런 유형은 이진 탐색으로 해결할 수 있어요!

🎯 핵심 아이디어

1. 답의 범위: 1 ~ 배열의 최댓값
2. 이진 탐색: 특정 값을 최대 공 개수로 만들 수 있는지 확인
3. 검증 함수: 주어진 연산 횟수로 목표를 달성할 수 있는지 계산

🔍 핵심 공식 이해하기

가방에 n개의 공이 있고, 최대 k개씩 나누고 싶다면 몇 번 나누어야 할까요?

필요한 나누기 횟수 = ceil(n / k) - 1

왜 이런 공식일까요?

• n개를 k개씩 나누면 ceil(n/k)개의 가방이 생깁니다
• 원래 1개 가방이 ceil(n/k)개가 되려면, ceil(n/k) - 1번 나누어야 합니다

📊 예시로 확인하기

• 9개 공을 최대 3개씩: ceil(9/3) - 1 = 3 - 1 = 2번 나누기
• 8개 공을 최대 2개씩: ceil(8/2) - 1 = 4 - 1 = 3번 나누기

🌟 마무리

시간 복잡도: O(n × log(max(nums)))

• 이진 탐색: O(log(max(nums)))
• 각 검증: O(n)

이 문제는 "최소값의 최대값"을 구하는 전형적인 이진 탐색 문제입니다. 핵심은 **"특정 값을 목표로 달성 가능한가?"**를 효율적으로 판단하는 것이죠.

비슷한 문제들을 더 풀어보면서 이진 탐색의 패턴을 익혀보세요! 💪

 

Code

Python

class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:

        # 주어진 balls를 최대 공 개수로 하여 목표를 달성할 수 있는지 확인하는 함수
        def verify(balls : int) -> bool:
            count = 0 # 필요한 연산 횟수

            for num in nums:
                # 예: 9개를 최대 3개씩 나누려면 -> 3개씩 3개 가방 = 2번 나누기 필요
                # 공식: (전체 공 개수 / 목표 개수) + (나머지가 있으면 1) - 1
                count += num // balls - 1

            return count <= maxOperations

        # 이진 탐색의 범위 설정
        start = 1 # 최소 벌점 (가방에 최소 1개의 공은 있어야 함)
        end = max(nums) # 최대 벌점 (현재 가장 큰 가방의 공 개수
        result = 0

        # 이진 탐색으로 최소 벌점 찾기
        while start <= end:
            mid = (start + end) // 2 # 중간값 (목표 최대 공 개수)

            # mid를 최대 공 개수로 만들 수 있는지 확인
            if verify(mid):
                result = mid # 가능하면 결과 저장
                end = mid -1 #  더 작은 값도 가능한지 확인 (왼쪽 탐색)
            else:
                start = mid + 1;  # 불가능하면 더 큰 값 필요 (오른쪽 탐색)

        return result

Java

class Solution {
   int[] nums;
    int maxOperations;

    public int minimumSize(int[] nums, int maxOperations) {
        
        this.nums = nums;
        this.maxOperations = maxOperations;
        
        // 이진 탐색의 범위 설정
        int start = 1;  // 최소 벌점 (가방에 최소 1개의 공은 있어야 함)
        int end = Arrays.stream(nums).max().getAsInt();  // 최대 벌점 (현재 가장 큰 가방의 공 개수)
        int result = 0;

        // 이진 탐색으로 최소 벌점 찾기
        while(start <= end){
            int mid = (start + end) / 2;  // 중간값 (목표 최대 공 개수)

            // mid를 최대 공 개수로 만들 수 있는지 확인
            if(verify(mid)){
                result = mid;  // 가능하면 결과 저장
                end = mid - 1;  // 더 작은 값도 가능한지 확인 (왼쪽 탐색)
            }else{
                start = mid + 1;  // 불가능하면 더 큰 값 필요 (오른쪽 탐색)
            }
        }

        return result;
    }

    // 주어진 balls를 최대 공 개수로 하여 목표를 달성할 수 있는지 확인하는 함수
    public boolean verify(int balls){
        long count = 0;  // 필요한 연산 횟수

        for(int num : this.nums){
            if(num > balls){
                // 현재 가방의 공이 목표보다 많으면 나누기 필요
                // 예: 9개를 최대 3개씩 나누려면 -> 3개씩 3개 가방 = 2번 나누기 필요
                // 공식: (전체 공 개수 / 목표 개수) + (나머지가 있으면 1) - 1
                count += (num / balls) + (num % balls != 0 ? 1 : 0) - 1;
                
            }
        }
        
        // 필요한 연산 횟수가 주어진 최대 연산 횟수 이하인지 확인
        return count <= this.maxOperations;
    }
}

Javascript

Math.max() 사용법 

// ❌ 잘못된 사용법
let end = Math.max(nums);  // NaN 반환

// ✅ 올바른 사용법
let end = Math.max(...nums);  // 스프레드 연산자 사용

var minimumSize = function(nums, maxOperations) {

    // 주어진 balls를 최대 공 개수로 하여 목표를 달성할 수 있는지 확인하는 함수
    const verify = (balls) =>{

        let count = 0; // 필요한 연산 횟수

        nums.forEach(num=>{
            // 예: 9개를 최대 3개씩 나누려면 -> 3개씩 3개 가방 = 2번 나누기 필요
            // 공식: (전체 공 개수 / 목표 개수) + (나머지가 있으면 1) - 1
            count += Math.ceil(num / balls) - 1;
        });

        // 필요한 연산 횟수가 주어진 최대 연산 횟수 이하인지 확인
        return count <= maxOperations;
    }



    // 이진 탐색의 범위 설정
    let start = 1;  // 최소 벌점 (가방에 최소 1개의 공은 있어야 함)
    let end = Math.max(...nums);  // 최대 벌점 (현재 가장 큰 가방의 공 개수)
    let result = 0;

    // 이진 탐색으로 최소 벌점 찾기
    while(start <= end){
        const mid = Math.floor((start + end) / 2);  // 중간값 (목표 최대 공 개수)

        // mid를 최대 공 개수로 만들 수 있는지 확인
        if(verify(mid)){
            result = mid;  // 가능하면 결과 저장
            end = mid - 1;  // 더 작은 값도 가능한지 확인 (왼쪽 탐색)
        }else{
            start = mid + 1;  // 불가능하면 더 큰 값 필요 (오른쪽 탐색)
        }
    }

    return result;
};