[codility] MinAvgTwoSlice

MinAvgTwoSlice

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

Task Score

100%

Correctness

100%

Performance

100%

---

correctness 100%에 performance 20%인 코드..

솔직히 이중 for문 넣으면서 시간초과 나올거란건 예상했다 ㅎㅎ..

나올 수 있는 모든 경우의 수를 다 배열에 넣어서 하나하나 다 값을 비교했다. 항상 느끼는거지만 이렇게 설명하면서 왜 점수가 낮게 나오는지 충분히 알게되는 것 같다.ㅋㅋ

 
x
// 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) {
        double[][] arr = new double[A.length - 1][A.length];
        double min = (A[0] + A[1]) / 2;
        int minKey = 0;
        /*System.out.println("min : " + min);*/
        
        for (int i = 0; i < A.length - 1; i++) {
            arr[i][i + 1] = A[i] + A[i + 1];
            
            for (int j = i + 2; j < A.length; j++) {
                arr[i][j] = arr[i][j - 1] + A[j];
            }
        }
        
        for (int i = 0; i < A.length - 1; i++) {
            
            for (int j = i + 1; j < A.length; j++) {
                arr[i][j] /= (j - i + 1);
                /*System.out.println(arr[i][j]);*/
            }
        }
        
        for (int i = 0; i < A.length - 1; i++) {
            
            for (int j = i + 1; j < A.length; j++) {
                
                if (min > arr[i][j]) {
                    min = arr[i][j];
                    minKey = i;
                    
                /*System.out.println("min: " + min);
                System.out.println("minKey: " + minKey);*/
                }
            }
        }
        
        return minKey;
    }
}

 

최소 평균이 나오는 경우는 인자가 2개 또는 3개일 때라고 하는데 왜..? 대체왜..?

아무튼 그렇다고해서 그렇게 풀어봤다..

아직도 이해할 수 없는.. 어떻게 증명할수있지..

 
x
// 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) {
        int answer = 0;
        double avg = Double.MAX_VALUE;
        
        for (int i = 0; i < A.length - 2; i++) {
            double avg2 = (A[i] + A[i + 1]) / 2.0;
            double avg3 = (A[i] + A[i + 1] + A[i + 2]) / 3.0;
            
            if (avg > Math.min(avg2, avg3)) {
                avg = Math.min(avg2, avg3);
                answer = i;
            }
            
            /*System.out.println(avg2);
            System.out.println(avg3);
            System.out.println(avg + "," + answer);*/
        }
        
        if (avg > (A[A.length - 2] + A[A.length - 1]) / 2.0) {
            avg = (A[A.length - 2] + A[A.length - 1]) / 2.0;
            answer = A.length - 2;
        }
        
        return answer;
    }
}