[코딜리티] MinAvgTwoSlice (javascript)

 

문제 출처

문제 요약

A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).

임의로 배열을 slice 해서 각 요소의 평균값을 구하고 평균값이 최소인 경우의 index 를 return 한다.

최소한 2개이상 원소를 slice 한다

문제 풀이

function solution(A) {
    let minIndex = 0;
    let minAvg = (A[0] + A[1]) / 2;

      for (let i = 0; i < A.length - 1; i++) {
        let sum = A[i];
        for (let j = i + 1; j < A.length; j++) {
          sum += A[j];
          const avg = sum / (j - i + 1);
          if (minAvg > avg) {
            minAvg = avg;
            minIndex = i;
          }
        }
      }

      return minIndex;
}

성능 상관없이 풀어봄.

당연히 Performance 에서 실패.

이 문제는 도저히 못 풀겟어서 구글의 힘을 빌렸다.

function solution(A) {
    let min = (A[0] + A[1]) / 2;
    let minIdx = 0;
    for ( let i = 1; i < A.length - 1 ; i ++ ) {
        let two = (A[i] + A[i + 1]) / 2;
        if (i > A.length - 2) {
            if ( two < min) {
                min = two;
                minIdx = i;
            }
        } else {
            let three = (A[i] + A [i + 1] + A[i + 2]) / 3;
            if (two < min || three < min) {
                min = two < three ? two : three;
                minIdx = i;
            }
        }
    }
    return minIdx;
}

결론

결론적으로 2가지 케이스만 고려하면 된다. slice가 2개 또는 3개인 경우이다. 평균의 성질로 부분집합의 평균은 가장 작은 인자보다 항상 크다. 즉, (1, 2)의 평균은 1.5이므로 1보다 크다는 의미이다.

또한, 평균들의 평균은 각 인자들의 평균과 같다. 즉, (1, 2, 3, 4)가 있을 때, (1, 2, 3, 4) = 2.5이고 (1, 2) = 1.5, (3, 4) = 3.5 일 때 (1.5, 3.5) = 2.5가 된다는 의미이다.

위 2가지 성질을 생각하였을 때 인자의 수가 4개 이상인 것은 고려할 필요가 없다. 가장 작은 평균을 가지는 부분집합은 가장 작은 숫자를 포함한 2개 또는 3개의 인자만 생각하면 된다.

3개의 인자를 고려하는 것은 2개의 부분집합으로는 3개의 부분집합을 구할 수 없기 때문이다. 가령 (1, 5, 2)가 있을 때, (2, 6, 1) = 3이고, (2, 6) = 4, (6, 1) = 3.5 일 때 (4, 3.5) = 3.75가 됨으로 3개의 경우는 따로 생각해야 한다.

기본적으로 수학적 지식이 있으면 좋았을 문제.