[Javascript] Codility Lesson 5 - MinAvgTwoSlice

 

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

 

문제 요약:

• 배열 A가 주어지고 해당 배열을 임의로 잘랐을 때, 평균값이 최소가 되는 시작 인덱스(P)를 구하시오.
  • (A[P] + A[P + 1] + ... A[Q]) / (Q - P + 1)
  • 0 ≤ P < Q < N
• 배열 A의 요소는 −10,000 ~ 10,000 사이의 숫자
• 배열 A의 요소 개수는 2개 이상 100,000개 이하

 

처음 풀이:

시간복잡도는 O(N ** 3)이 나왔다. 배열을 처음부터 끝까지 순환하며 시작 인덱스를 지정하고, 시작 인덱스를 기준으로 개수를 한 개씩 증가시키며 평균값을 구한 뒤, 해당 평균값이 가장 작은 평균값인지 아닌지 판단하는 방식이다. 퍼포먼스 측면에서 매우 비효율적이기 때문에 개선 시도를 했다.

function solution(A) {
    const cnt = A.length;
    let i = 0;
    let index = 0;
    let minAvg = Math.max(…A);

    const sliceAvg = (list, start, cnt) => {
        let sliceArr = list.slice(start, start + cnt);
        let sum = sliceArr.reduce((prev, curr) => {
            return prev + curr;
        }, 0);
        return sum / cnt;
    };

    while (i < A.length - 1) {
        for (let x = 2; x <= cnt - i; x++) {
            let tmp = sliceAvg(A, i, x);
            index = tmp < minAvg ? i : index;
            minAvg = tmp < minAvg ? tmp : minAvg;
        };
        i += 1;
    };

   return index;
}

 

 

개선시도1:

더할 값이 평균 값보다 작다면 해당 값을 더한 평균 값은 기존의 평균 값보다 작다는 생각에서 아래와 같은 코드를 작성했다. 예를 들어 (10 + 11) / 2 = 10.5 이면  10.5보다 작은 10을 합친 평균값은 (10 + 11 + 10) / 3 = 10.333... 이 되고, 10.5보다 큰 11을 합친 평균값은 (10 + 11 + 11) / 3 = 10.666... 이 된다. 조건을 통해 연산이 필요 없는 경우를 건너뛰는 방식이지만 시간 복잡도는 O(N ** 2)로 퍼포먼스는 크게 개선되지 않았다.

function solution(A) {
    const cnt = A.length;
    let i = 0;
    let index = 0;
    let minAvg = Math.max(…A);

    const sliceAvg = (list, start, cnt) => {
        let sliceArr = list.slice(start, start + cnt);
        let sum = sliceArr.reduce((prev, curr) => {
            return prev + curr;
        }, 0);
        return sum / cnt;
    };

    while (i < A.length - 1) {
        if (A[i] > minAvg) {
            i += 1;
            continue;
        };

        for (let x = 2; x <= cnt - i; x++) {
            let tmp = sliceAvg(A, i, x);
            index = tmp < minAvg ? i : index;
            minAvg = tmp < minAvg ? tmp : minAvg;
        };
        i += 1;
    };

   return index;
};

 

 

개선시도2: 

숫자 2개의 평균은 두 숫자 중 작은 값보다 크거나 같다(두 숫자가 동일한 경우). (10 + 4) / 2 = 7 → 평균값 7은 최솟값 4보다 크다. 확대해서 생각하면 임의의 숫자들의 평균은 숫자들을 두 그룹으로 분리했을 때 둘 중 합이 더 작은 그룹보다 크다 (평균값 >= 두 그룹 중 최솟값). 숫자 3개일 때도 생각을 해야하는데, 숫자 2개로는 짝수개의 숫자에 대해서만 조합이 가능하기 때문이다. 이런 방향으로 풀이했을 때 순환 1번에 답을 구할 수 있으며 시간 복잡도는 O(N)이다.

참고: https://nukeguys.tistory.com/175

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

    for (let i = 2; i < A.length; i++) {
        let tmp = (A[i] + A[i - 1] + A[i - 2]) / 3;
        if (tmp < minAvg) {
            minAvg = tmp;
            index = i - 2;
        }

        tmp = (A[i] + A[i - 1]) / 2;
        if (tmp < minAvg) {
            minAvg = tmp;
            index = i - 1;
        };
    };

   return index;
};