[코딩테스트] Codility 5-4 MinAvgTwoSlice (JavaScript) - 평균의 수학적 특성 활용

문제 링크 : https://app.codility.com/programmers/lessons/5-prefix_sums/min_avg_two_slice/

 

 

Solution

정답률 : 100%

시간복잡도 : O(N)

 

시간복잡도를 줄이기 위해 수학적 인사이트가 필요했다.

 

• 두 수의 평균은 두 수 중 작은 수보다 크거나 같다
• 정수 m, n이 있고, m <= n 일 경우, 두 수의 평균은 m보다 크다
• 정수 k, l, m, n 이 있고, (k+l) <= (m+n) 일 경우, 네 수의 평균은 (k+l) 보다 크다
• 따라서 숫자가 2개 또는 3개일 때 평균이 최소값이 된다.

 

연속한 엘리먼트가 2대 또는 3개인 경우만 고려하여 코드를 작성하면 된다.

 

function solution(A) {
  let min = Number.MAX_SAFE_INTEGER;
  let minIdx;

  let Length = A.length

  for (let i=0; i<Length; i++) {

    if (i+1<Length) {
      let avg = (A[i] + A[i+1]) / 2
      if (avg<min) {
        min = avg;
        minIdx = i;
      }
    }

    if (i+2<Length) {
      let avg = (A[i] + A[i+1] + A[i+2]) / 3
      if (avg<min) {
        min = avg;
        minIdx = i;
      }
    }

  }
  return minIdx;
}