0. 문제

You are given a 0-indexed integer array candies. Each element in the array denotes a pile of candies of size candies[i]. You can divide each pile into any number of sub piles, but you cannot merge two piles together.

You are also given an integer k. You should allocate piles of candies to k children such that each child gets the same number of candies. Each child can be allocated candies from only one pile of candies and some piles of candies may go unused.

Return the maximum number of candies each child can get.

Example 1:

• Input: candies = [5,8,6], k = 3
• Output: 5
• Explanation: We can divide candies[1] into 2 piles of size 5 and 3, and candies[2] into 2 piles of size 5 and 1. We now have five piles of candies of sizes 5, 5, 3, 5, and 1. We can allocate the 3 piles of size 5 to 3 children. It can be proven that each child cannot receive more than 5 candies.

Example 2:

• Input: candies = [2,5], k = 11
• Output: 0
• Explanation: There are 11 children but only 7 candies in total, so it is impossible to ensure each child receives at least one candy. Thus, each child gets no candy and the answer is 0.

Constraints:

• 1 <= candies.length <= 105
• 1 <= candies[i] <= 107
• 1 <= k <= 1012

1. 필요한 개념

이진 탐색 (Binary Search)

• 분배할 사탕의 개수를 빠르게 찾기 위해 이진 탐색을 도입할 필요가 있음.
• 특정 구간의 중간값을 찾아서 목표값과 비교 후, 구간의 왼쪽 절반, 혹은 오른쪽 절반에서 다시 이진탐색을 실시. 계속해서 탐색 범위가 줄어들기 떄문에, 시간복잡도가 낮음.

public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;  // 중간값 계산

            if (arr[mid] == target) {
                return mid; // 찾으면 인덱스 반환
            } else if (arr[mid] < target) {
                left = mid + 1; // 오른쪽 탐색
            } else {
                right = mid - 1; // 왼쪽 탐색
            }
        }

        return -1; // 찾지 못함
    }

2. 정답코드

시간 복잡도

$O(NLogM)$

구현 중 발생한 문제

선형탐색 O(N):

파라미터의 크기가 작은 경우에는 문제가 없었지만, 초기에 활용한 선형탐색은 파라미터의 크기가 커질수록 연산 시간이 크게 증가해 runtime error가 뜨는 경우가 발생.

type overflow:

checkAllocation()의 리턴을 초기에 int로 설정해, long k와 비교하는 연산을 구현했으나, 리턴이 int의 범위를 넘어서는 경우, k와의 유의미한 비교 연산이 불가능해짐.

class Solution {
  public int maximumCandies(int[] candies, long k) {
    long maxChildren = 0;

    // 가장 큰 pile 찾기
    int maxPile = 0;
    for (int pile: candies)
      if (maxPile < pile)
        maxPile = pile;

    // 이진 탐색을 위한 인덱스
    int left = 0;
    int right = maxPile;

    // 사탕 개수에 대한 이진 탐색
    while (left < right) {
      int middle = (left + right + 1) / 2;

      maxChildren = checkAllocation(candies, middle);
      if (maxChildren >= k) {
        left = middle;
      } else {
        right = middle - 1;
      }
    }
    return left;
  }

  // middle개의 사탕을 받을 수 있는 아이들의 수
  public long checkAllocation(int[] candies , int maxCandies) {
    long maxChildren = 0;
    for (int pile: candies) {
      maxChildren += pile / maxCandies;
    }
    return maxChildren;
  }
}