이진탐색 문제 (SV2 과자 나눠주기)

문제

16401 과자 나눠주기 (SV2)

https://www.acmicpc.net/problem/16401

알고리즘 분류: 이진 탐색

풀이

입력으로 주어진 과자의 길이 중 최대 값을 기준으로 한다.

const start = 1;
const end = Math.max(...array);

이후 이진탐색으로 계산하여 매 중간값으로 주어진 과자의 길이들을 나눈 몫을 다 더해 더한 값이 조카의 수보다 작거나 혹은 크거나 같을 때를 비교하여 start와 end 값을 조정한다.

처음 코드를 작성할 때는 주어진 과자를 mid로 모두 계산을 하고 새로운 배열에 저장했다. 그리고 이 새로운 배열의 원소들의 합을 구했다.

function binary_search(array, start, end) {
  let result = 0;
  while (start <= end) {
    const mid = Math.floor((start + end) / 2);
    const newArr = array.map((element) => Math.floor(element / mid));
    const sum = newArr.reduce((ac, cv) => ac + cv, 0);
    if (sum >= M) {
      result = mid;
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return result;
}

그러나 이 방법은 나눈 몫이 0일 때도 계산을 해야하고 새로운 배열 또한 생성해야 한다.
따라서 이 방법은 시간복잡도나 공간 복잡도 측면에서 좋지 않다.

보완한 코드 작성

function binary_search(array, start, end) {
  let result = 0;
  while (start <= end) {
    let sum = 0;
    const mid = Math.floor((start + end) / 2);
    for (let i = 0; i < N; i++) {
      if (array[i] >= mid) {
        sum += Math.floor(array[i] / mid);
      }
    }

    // ...생략
}