[코딜리티] codility lesson 5 Frefix Sums - MinAvgTwoSlice 100%

문제.

Programming language:                 C                        C++                        C#                        Go                        Java                        JavaScript                        Lua                        Objective-C                        Pascal                        PHP                        Perl                        Python                        Ruby                        Scala                        Swift 2                        Swift 3                        VB.NET                    

A non-empty zero-indexed 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:

int solution(int A[], int N);

that, given a non-empty zero-indexed 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), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Copyright 2009–2017 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

풀이.

1234567891011121314151617181920212223242526272829303132

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int idx = 0;
        float result = Float.MAX_VALUE;
        
        for(int i = 0 ; i < A.length ; i++){
            if(i+1 < A.length){
                if( result > (A[i] + A[i+1])/2f){
                    result = (A[i] + A[i+1])/2f ;
                    idx = i;                    
                }
            }
            
            if(i+2 < A.length){
                if( result > (A[i] + A[i+1] + A[i+2])/3f){
                    result = (A[i] + A[i+1] + A[i+2])/3f ;
                    idx = i;                    
                }
            }
        }
        
        return idx;
        
    }
}

설명.

슬라이스 란 배열 A 의 연속된 부분집합이다. (두개 이상, 연속적 일 것.)
그 슬라이스의 평균 값이 제일 작은 때 시작위치를 리턴 하라.

이건 수학적 지식이 있었다면 좀 쉽게 풀릴 수 있다.( 나는 없었지 ㅜㅜ )
전제는
1. 2개 인자의 평균은 항상 2개중 한개의 인자보다 값이 크다.
2. 평균들의 평균은 각 인자들의 평균과 같다.
(여기서 1전제에 의해 평균들의 평균은 그 인자가 되는 평균들 보다 항상 크다.)

그러므로 최소 단위인 2개 의 평균들중 가작 작은 값만 있으면 된다.

그런데 하나의 경우의 수가 더 필요하다.
그건 바로. 인자가 3개인 경우 이다.
4개의 부분 집합은 0개 1개 2개 3개 4개 가 있다.
이 문제에서 부분집합 0개는 필요 없다.
각 인자 하나를 뜻하는 부분집합 1개는 필요 없다.
4개의 의 부분집합은 곧 2개의 부분집합 으로 표현되므로 1전제 만으로 충분
(4개의 부분집합은 2개의 부분집합의 평균들의 평균 이므로 항상 큼)
하지만 3개를 인자로 하는 부분집합 도 고려 해야 한다.
(2개의 부분집합들로 3개의 부분집합 을 구할 수 없음)

그래서 2개 와 3개의 평균들만 고려 하면 된다.

요약.
부분집합중 가장 작은 집합의 평균이 항상 작다.
모든 부분집합은 2와 3으로 모두 표현된다. 그러나 그것은 값이 항상 크다.(전제 1)


끝.