Codility_MinAvgTwoSlice

5-4. 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가 주어집니다. 0 ≤ P < Q < N인 두 정수 (P, Q) 쌍은 배열 A의 슬라이스라고 합니다 (슬라이스는 최소 두 개의 요소를 포함합니다). 슬라이스 (P, Q)의 평균은 A[P] + A[P + 1] + … + A[Q]의 합을 슬라이스의 길이로 나눈 값입니다. 정확히 말하면, 평균은 (A[P] + A[P + 1] + … + A[Q]) / (Q − P + 1)입니다.

예를 들어, 배열 A가 다음과 같다면:

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

다음과 같은 예제 슬라이스가 포함됩니다:

슬라이스 (1, 2), 평균은 (2 + 2) / 2 = 2;
슬라이스 (3, 4), 평균은 (5 + 1) / 2 = 3;
슬라이스 (1, 4), 평균은 (2 + 2 + 5 + 1) / 4 = 2.5.
목표는 평균이 최소인 슬라이스의 시작 위치를 찾는 것입니다.

비어 있지 않은 N개의 정수로 구성된 배열 A가 주어지면, 평균이 최소인 슬라이스의 시작 위치를 반환합니다. 평균이 최소인 슬라이스가 여러 개 있는 경우, 그러한 슬라이스의 가장 작은 시작 위치를 반환해야 합니다.

예를 들어, 배열 A가 다음과 같다면:

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

함수는 1을 반환해야 합니다.

다음 가정을 위한 효율적인 알고리즘을 작성하세요:

N은 [2…100,000] 범위 내의 정수입니다.
배열 A의 각 요소는 [−10,000…10,000] 범위 내의 정수입니다.

---

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A) {
        int N = A.length;
        int minIndex = 0;
        double minAvg = (A[0] + A[1]) / 2.0;

        for (int i = 0; i < N - 2; i++) {
            double avg2 = (A[i] + A[i + 1]) / 2.0;
            double avg3 = (A[i] + A[i + 1] + A[i + 2]) / 3.0;

            if (avg2 < minAvg) {
                minAvg = avg2;
                minIndex = i;
            }
            if (avg3 < minAvg) {
                minAvg = avg3;
                minIndex = i;
            }
        }

        double lastAvg = (A[N - 2] + A[N - 1]) / 2.0;
        if (lastAvg < minAvg) {
            minAvg = lastAvg;
            minIndex = N - 2;
        }

        return minIndex;
    }
}

예제로 주어진 슬라이스의 평균을 계산해보면 보통 2,3선에서 끊기는 평균이 그 이상보다 작은 것을 볼 수 있습니다.
길이가 2,3인 모든 평균을 계산하면서 최소 평균을 찾습니다. 추가적으로 평균을 찾을때 최소 평균을 찾은 슬라이스의 시작인덱스를 업데이트해줍니다.

처음 제출시에 틀렸던 부분으로 주의 할 점은 for문을 사용시에 배열A의 크기만큼 for문을 돌리면
평균값을 구할 때 ->
double avg2 = (A[i] + A[i + 1]) / 2.0;
double avg3 = (A[i] + A[i + 1] + A[i + 2]) / 3.0;
i + 1, i + 2 때문에 배열 범위에서 나가버리는 문제가 발생하기 때문에 반복문에서는 반복범위를 N - 2까지 잡아주고 반복문이 끝난 후 마지막 슬라이스 요소를 따로 계산해줍니다.

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/5-prefix_sums/min_avg_two_slice/