Lesson5. Prefix Sums - MinAvgTwoSlice

MinAvgTwoSlice - Find the minimal average of any slice containing at least two elements.

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

문제요약

길이가 N인 정수 배열 A와 0<=P<Q<N인 (P,Q)가 주어지면 A[P] + ... + A[Q]의 산술평균을 구할 수 있다. A에서 가장 작은 평균을 갖는 범위의 시작 위치(P)를 찾아라.

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

풀이

알면 풀고 모르면 못푸는 문제. 평균의 특징을 생각해보면 어떤 두 수의 평균이 있을 때 그 평균은 두 수 중 작은 수 이상값이 된다.(같은 경우는 두 수가 같은 경우) 어떤 두 그룹을 고려해도 두 그룹의 각각의 평균이 있을 때 전체의 평균은 각 그룹 평균 중 작은 값 이상이 된다. 큰 쪽에서 작은 쪽으로 수를 나눠줘서 같게 만드는게 평균이라고 생각하면 이해가 쉽다. 즉 가능한 부분순열의 평균의 최솟값을 찾아야 하지만 앞에 언급한 내용에 따라 작은 수의 그룹의 평균의 최솟값만 찾으면 그 그룹을 포함하는 어떤 그룹은 그 평균보다 작아질 수 없다. 예로 원소가 4개인 그룹의 평균은 앞 2개와 뒤 2개씩 나누었을 때 각각의 평균의 작은 값보다 작아질 수 없으므로 2개인 그룹을 고려하면 4개인 그룹은 확인할 필요가 없어진다. 그럼 최소 그룹의 단위를 정해야 하는데, 2개인 그룹은 당연히 필요하다. 또한 추가로 3개인 그룹을 확인해야 하는데 3개는 2개와 1개로 나누게 되면 1개인 경우를 확인해야 하는데, 주어진 조건에 의해 그룹은 2개 이상이다.(P<Q이므로) 따라서 2개와 3개인 그룹들만 모두 확인하면 나머지 크기에 대해서는 고려할 필요가 없어진다.