Codility - MinAvgTwoSlice

문제

배열 A의 두 개 이상의 원소로 구성된 부분배열의 평균이 가장 작은 부분배열의 시작 index를 구하라

분석

• 수학을 알면 더 간단하게 풀리는 문제였다.
• 부분배열 (a, b)와 (c, d)가 있을 때, Avg(a, b) < Avg(c, d)라면, Avg(a, b) < Avg(a, b, c, d) < Avg(c, d)가 항상 성립하므로 4개 이상의 부분배열은 탐색할 필요 없음
• 따라서 2, 3개 원소로 구성된 부분배열만 탐색

코드

const solution = (A) => {
  let [minVal, minIdx] = [
    (A[A.length - 1] + A[A.length - 2]) / 2,
    A.length - 2
  ];

  for (let i = minIdx - 1; i >= 0; i--) {
    let sumOfTwo = A[i] + A[i + 1];
    let sumOfThree = sumOfTwo + A[i + 2];

    let currMinVal = Math.min(sumOfTwo / 2, sumOfThree / 3);

    if (currMinVal <= minVal) [minVal, minIdx] = [currMinVal, i];
  }

  return minIdx;
};