[Codility] Lesson 5 : MinAvgTwoSlice - JAVA

문제

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].
 
Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

solution(int[] A)에 입력되는 배열 A의 길이(N)는 2 ~ 100,000이고
배열 A에 저장되는 element의 범위는 -10,000 ~ 10,000이다.
그리고 배열 A의 범위를 P부터 Q까지로 나눌 수 있다. (0 ≤ P < Q < N)

배열 A가 {4, 2, 2, 5, 1, 5, 8}일 때 (P, Q)를 통해 평균 값을 구한다.
        - P=1, Q=2이면 A[1] + A[2] / 2     =     (2 + 2) / 2 = 2
        - P=3, Q=4이면 A[3] + A[4] / 2     =     (5 + 1) / 2 = 3
        - P=1, Q=4이면 A[1] + A[2] + A[3] + A[4] / 4     =     (2 + 2 + 5 + 1) / 4 = 2.5

이 때 평균값이 가장 작은 경우 시작 인덱스 번호(starting point)를 반환해준다.

 

풀이 - 1

class Solution {
    public int solution(int[] A) {
        double min = Integer.MAX_VALUE;
        int startPoint = 0;
        
        for(int i=0; i<A.length-1; i++) {
            int sum = A[i];
            for(int j=i+1; j<A.length; j++) {
                sum += A[j];
                double avg = (double)sum / (double)(j-i+1);
                min = Math.min(min, avg);
                if(min == avg) startPoint = i;
            }
        }	
        return startPoint;
    }
}

 

'풀이 - 1'에 대한 회고

 

일단 O(n*n)이 나와도 반복문을 이용해보자고 생각하고 소스코드를 작성했다.

역시 결과는 50%

 

 

그런데 정확도도 100%가 아니다.

퍼포먼스는 왜 20%이지?

다른 사람들은 어떻게 했는지 우선 봐야겠다.

 

 

다른 사람의 풀이

class Solution {
    public int solution(int[] A) {
        float min = (A[0] + A[1]) / 2.f;
        int startPoint = 0;
        for (int i = 2; i < A.length; ++i) {
            // 3개 범위일때 평균값
            float avg = (A[i] + A[i - 1] + A[i - 2]) / 3.f;
            
            // 가장 작은 평균 값일 경우 P의 값을 갱신한다.
            if (avg < min) { 
                min = avg;
                startPoint = i - 2;
            }
            
            // 2개 범위일때 평균값
            avg = (A[i] + A[i - 1]) / 2.f; 
            if (avg < min) {
                min = avg;
                startPoint = i - 1;
            }
        }
        return startPoint;
    }
}

 

'다른 사람의 풀이'를 통한 회고

 

이번 문제는 부분 평균값을 비교하는 문제라고 한다.

먼저 문제에 제시된 배열의 일부를 이용해서 풀이를 이해해 봤다.

A = {a, b, c, d}일 때
(a+b) / 2 <= (c+d) / 2일 때 평균은 (a+b) / 2 이상이라고 한다.

그리고 (a+b+c+d) / 4는 (a+b) / 2와 (c+d) / 2 사이의 숫자이기 때문에
굳이 4개의 숫자를 비교할 필요는 없다.

예를 들어 A = {4, 2, 2, 5}일 때
        (4+2) / 2 = 3
        (2+5) / 2 = 3.5 이므로
(4+2)의 시작 index를 반환해주면 된다.

단, 숫자가 3개인 경우도 같이 고려해줘야 한다.
위에서 (4+2) / 2의 평균값이 가장 작았지만
(4+2+2) / 3의 평균값(2.xx)과 한번 더 비교해줘야 한다는 말이다.
마찬가지로 (2+2+5) / 3의 평균값(3)과도 비교해주면
가장 작은 평균이 어느 인덱스부터 시작하는지 알 수 있다.

 

이 방식으로 풀었더니

 

정확도와 퍼포먼스가 모두 100%가 되었다.

 

 

또한 가장 중요한 시간복잡도!

반복문을 한 번만 사용하면 되기 때문에 시간복잡도는 O(n)이 나왔다.

이번 문제를 통해 느낀건데 수학 문제를 열심히 공부해야겠다.