[Codility] Lesson5 MinAvgTwoSlice

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

MinAvgTwoSlice coding task - Learn to Code - Codility

 

문제설명

간단히 설명하면, N 길이의 배열 A에 대해서 0 <= P < Q < N 인 P, Q가 존재할 때,

Slice(P, Q) = 배열 A[P] ~ A[Q] 까지의 합의 평균 이다.

 

처음에 무턱대고 Brute Force 로 풀었을 때, 무려 O(N**3) 이라는 시간복잡도가 나왔다.

아무리 생각해봐도 어떻게 시간복잡도를 O(N)으로 줄일 수 있을지.. 떠오르지 않았다.

결국은 구글링을 했고, 수학적 지식(?) 이 있어야 해결할 수 있는 문제임을 알게 되었다.

 

풀이

문제 풀이의 핵심은 아래와 같다.

 

(a,b) 의 평균값은 a, b 두 수 중 작은 숫자보다 무조건 크거나 같다.

 -> a, b 두 수가 같을 경우, (a, b)의 평균값 == a, b 이다.

 

이를 확장하면,

 

(a,b,c,d)의 평균값은 (a,b)의 평균값과 (c,d)의 평균값 중 작은 값보다 무조건 크거나 같다.

 

그럼, 원소의 개수가 홀수 개인 경우는?

 

(a,b,c,d,e)의 평균값은 (a,b,c)의 평균값과 (d,e)의 평균값 중 작은 값보다 무조건 크거나 같다.

 

Slice 의 원소 개수가 >= 4 인 경우는, 원소개수가 2인 Slice 와 3인 Slice 의 조합으로 항상 만들 수 있으므로

원소 개수가 2이거나 3인 Slice 의 평균 값의 최솟값만 구해주면 된다.

 

// 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
        // 슬라이스 2개와 3개의 최솟값을 구해주면 됨.
​
        Float minVal = Float.MAX_VALUE;
        int minIdx = -1;
        
​
        // 2개 슬라이스 최솟값
        for(int i=0; i<A.length - 1; i++){
            float curVal = ((float)A[i] + A[i+1])/(float)2;
            if(minVal > curVal){
                minVal = curVal;
                minIdx = i;
            } 
        }
​
        // 3개 슬라이스 최솟값
        if(A.length >= 3){
            for(int i=0; i<A.length - 2; i++){
                float curVal = ((float)A[i] + A[i+1] +A[i+2]) / (float)3;
                if(minVal > curVal){
                    minVal = curVal;
                    minIdx = i;
                }
            }
        }
        
​
        return minIdx;
​
    }
}

 

이런 문제가 코테에 나왔을 때.. 저런 식으로 생각하고 풀 수 있을까?,,,,