[Codility] MinMaxDivision javascript

문제

https://app.codility.com/programmers/lessons/14-binary_search_algorithm/min_max_division/

풀이

블럭을 몇번 나눌 지를 이분 탐색으로 찾는다.

1. 나올 수 있는 가장 최고의 경우는 원소 길이만큼 나누는 것 -> 배열의 최대값이 최소값
2. 나올 수 있는 가장 큰 값은 배열 모든 원소의 합
3. 이분 탐색으로 나올 수 있는 값을 정해가면서 block 몇개로 나누어지는지 체크 후 주어진 K만큼 나눌 수 있을 때가 정답

코드

function getBlocks(A, midValue) {
  let blocks = 1;
  let subSum = 0;
  A.forEach((el) => {
    if (subSum + el > midValue) {
      blocks += 1;
      subSum = el;
    } else {
      subSum += el;
    }
  })
  return blocks;
}

function solution(K, M, A) {
  // write your code in JavaScript (Node.js 8.9.4)
  let minValue = A.reduce((acc, el) => {
    return Math.max(acc, el);
  }, 0);

  let maxValue = A.reduce((acc, el) => {
    return acc + el;
  }, 0);

  while (minValue < maxValue) {
    let midValue = parseInt((minValue + maxValue) / 2, 10);
    let blocks = getBlocks(A, midValue);
    if (blocks > K) {
      minValue = midValue + 1;
    } else {
      maxValue = midValue;
    }
  }

  return minValue;
}