Codility - [Lesson5] 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:

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

Assume that:

• 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].

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

문제요약

A 배열의 연속된 정수의 부분집합을 slice라 정의 하였을 때, 평균이 가장 작은 slice의 시작 인덱스 값을 구하여라.

문제풀이

결론적으로 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개의 경우는 따로 생각해야 한다.

def solution(A):
    n = len(A)
    min = 10001
    min_idx = 0
    for i in range(n):
        if i + 1 < n:
            avg = (A[i] + A[i+1]) / 2
            if avg < min:
                min = avg
                min_idx = i
        if i + 2 < n:
            avg = (A[i] + A[i+1] + A[i+2]) / 3
            if avg < min:
                min = avg
                min_idx = i
    return min_idx