'Algorithm'에 해당되는 글 23건

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.

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

  평균의 특성상 최소 평균은 두 평균을 낼때는 무조건 작은 값보다 크거나 같은 값이 평균이 된다.

따라서, 최소 평균은 최소 단위를 가지는 평균들 중에서만 나올 수 있다는 것을 쉽게 알 수 있다. 그러면 최소 단위만 생각을 하면 되는데 먼저 2개짜리는 가장 최소이므로 무조건 포함이되고 3개짜리 또한 2개와 1개의 형태로 구할 수 없기 때문에 최소 단위 중에 하나로 계산해야한다.

4개짜리는 2개 단위로 구성할 수 있기 때문에 무조건 2개 단위중 최소 값보다 크거나 같기 때문에 고려하지 않아도 된다. 그 위 단위들 또한 계산 상으로는 연관이 없어보이지만 잘 생각해본다면 무조건 최소 단위들 보다는 크거나 같은 값을 가질 것이라는걸 직관적으로 알 수 있다.

아래의 코드는 간단하게 2, 3개 연속되는 평균 중 최소값의 시작 index를 저장하는 코드이다.

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        double min;
        double twoAvg = 0;
        double threeAvg = 0;
        
        int idx = 0;
        
        min = (A[0] + A[1]);
        min /= 2;
        
        for(int i = 0; i < A.length-1; i++){
            
            twoAvg = (A[i] + A[i+1]);
            twoAvg /= 2;
            
            if(i < A.length-2){
                threeAvg = A[i] + A[i+1] + A[i+2];
                threeAvg /= 3;
            }
            
            if(twoAvg < min){
                min = twoAvg;
                idx = i;
            }
            if(threeAvg < min){
                min = threeAvg;
                idx = i;
            }
        }
        
        return idx;
    }
}