[Codility] MinAvgTwoSlice - JavaScript

Sohyeon Bak·2021년 12월 7일

Codility

목록 보기

9/19

문제

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).

For example, array A such that:

A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8

contains the following example slices:

slice (1, 2), whose average is (2 + 2) / 2 = 2;
slice (3, 4), whose average is (5 + 1) / 2 = 3;
slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.
The goal is to find the starting position of a slice whose average is minimal.

Write a function:

function solution(A);

that, given a non-empty array A consisting of N integers, returns the starting position of the slice with the minimal average. If there is more than one slice with a minimal average, you should return the smallest starting position of such a slice.

For example, given array A such that:

A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8

the function should return 1, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [2..100,000];
each element of array A is an integer within the range [−10,000..10,000].

문제해석

배열을 적어도 2개의 요소가 포함된 배열로 잘라서 평균값을 구하는데 가장 작은 평균값을 가진 배열의 첫번째 요소를 찾는 것이다.
즉, 길이가 N인 배열을 길이가 2부터 N까지 자를 수 있고, 그 자른 배열의 요소의 평균값을 구한 후 가장 작은 평균값을 가진 배열의 첫번째 인덱스 값을 리턴하는 문제이다.

문제는 여러 방법을 통해 쉽게 해결되지만 효율성에서 막히기 때문에 O(N)으로 문제 푸는 방법을 찾아야한다.
이 문제는 평균을 구하는 수학적인 방법을 통해 문제를 해결할 수 있다.

먼저 평균을 구하는 방법의 특징을 살펴봐야한다.

a와 b가 있을때 두 값의 평균은 두 수 중 작은 수보다 크다.
a < b일때, a와 b의 평균은 a보다 크다. (a=b라면, a 혹은 b가 평균이다.)
확장시켜 두 그룹의 평균을 구할 때도 똑같다.
a,b,c,d 중 (a, b) <= (c, d)일때, (a, b)와 (c, d)의 평균은 (a, b)이상이다.
즉 가장 작은 평균의 값을 구한다는 것은 두 그룹으로 나눴을때 작은 값보다 평균이 커진다는 것을 확인 할 수 있다. 최소 단위를 문제에서 2개로 지정했으니 2개로 가져가야하고, 추가로 3개인 그룹까지 확인해야한다.

문제풀이

가장 작은 기준인 2개를 포함한 요소의 평균값을 초기값으로 세팅한다.
배열을 돌면서 2개와 3개 요소가 포함된 배열의 평균값을 초기값과 비교해 작은 평균값을 찾는다.
초기값보다 배열을 돌면서 찾은 요소의 평균이 더 작다면 첫번째 요소의 인덱스를 답으로 지정한다.

코드

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

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

    return answer
}