[Codility - Java] 5. Prefix Sums - 4. MinAvgTwoSlice

MinAvgTwoSlice

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:

class Solution { public int solution(int[] 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].

---

N개의 정수로 이뤄진 비어있지 않은 배열 A

정수로 이뤄진 pair인 (P, Q)는 0 <= P < Q < N을 만족합니다.
pair (P, Q)는 배열 A의 요소를 slice한 것이고, 그 것의 평균은 (A[P] + A[P + 1] + ... + A[Q]) / (Q - P + 1) 입니다.
가장 평균이 작은 pair의 P값을 리턴하면 됩니다.

가장 작은 평균을 나타내는 시작점 P를 구하는 문제.

4개 이상의 수의 평균은, 어떻게 하더라도 2개나 3개로 구성한 평균보다 큽니다.

4 2 1 1 의 평균보다, 1 1 의 평균이 더 작은 것을 생각하면 됩니다.

방법 1. 누적 합을 이용하여 풀기.

누적합을 이용하여 countingArr를 계산하고,
누적합의 2요소간의 차, 3요소간의 차를 조회하여 가장 작은 평균값을 나타내는 시작점 P를 구하면 됩니다.

countingArr의 맨 첫번째는 0,
그 이후부터는 A의 요소를 합산한 값이 들어있습니다.

$A = [4, 2, 2, 5, 1, 5, 8]$
$countingArr = [0, 4, 6, 8, 13, 14, 19, 27]$

(0, 1) = (4 + 2)/2
(1, 2) = (2 + 2)/2
(1, 3) = (2 + 2 + 5)/3

countingArr에서 구하는 방법은
(0, 1) = (countingArr[2] - countingArr[0])/2
(1, 2) = (countingArr[3] - countingArr[1])/2
(1, 3) = (countingArr[4] - countingArr[1])/3

코드로 나타내면 아래와 같습니다.

static int minAvgTwoSlice(int[] A) {
    int[] countingArr = new int[A.length + 1];
    for (int i = 0; i < A.length; i++) {
        countingArr[i + 1] = countingArr[i] + A[i];
    }
    double minAvg = (countingArr[2] - countingArr[0])/2.0;
    int startingPosition = 0;
    for (int i = 2; i < A.length; i++) {
        double temp = (countingArr[i + 1] - countingArr[i - 1])/2.0;
        if(minAvg > temp) {
            minAvg = temp;
            startingPosition = i - 1;
        }
        temp = (countingArr[i + 1] - countingArr[i - 2])/3.0;
        if(minAvg > temp) {
            minAvg = temp;
            startingPosition = i - 2;
        }
    }
    return startingPosition;
}

방법 2.

누적합을 활용하지 않고, 배열 A의 각요소를 더해서 평균을 구해도 무관합니다.

static int minAvgTwoSlice(int[] A) {
    int minSlice = 0;
    double minAvg = (A[0] + A[1])/2.0;

    for (int i = 2; i < A.length; i++) {
        double temp = (A[i] + A[i - 1]) / 2.0;
        if(temp < minAvg) {
            minAvg = temp;
            minSlice = i - 1;
        }
        temp = (A[i] + A[i - 1] + A[i - 2]) / 3.0;
        if (temp < minAvg) {
            minAvg = temp;
            minSlice = i - 2;
        }
    }
    return minSlice;
}