260. MinAvgTwoSlice

1. JavaScript

참고

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const N = A.length;
    let minAvg = (A[0] + A[1]) / 2;
    let minIndex = 0;
    let avg = 0;

    for(let i=2; i<N; i++){
        avg = (A[i-2] + A[i-1] + A[i]) / 3;
        if(avg < minAvg){
            minAvg = avg;
            minIndex = i-2;
        }

        avg = (A[i-1] + A[i]) / 2;
        if(avg < minAvg){
            minAvg = avg;
            minIndex = i-1;
        }
    }

    return minIndex;

}

• 2가지 케이스만 고려하면 된다.

  • slice가 2개 또는 3개인 경우

• 평균의 성질로 부분집합의 평균은 가장 작은 인자보다 항상 크다.

  • 즉, (1, 2)의 평균은 1.5이므로 1보다 크다는 의미이다.

• 평균들의 평균은 각 인자들의 평균과 같다.

  • 즉, (1, 2, 3, 4)가 있을 때, (1, 2, 3, 4) = 2.5이고 (1, 2) = 1.5, (3, 4) = 3.5 일 때 (1.5, 3.5) = 2.5가 된다는 의미

• 위 2가지 성질을 생각하였을 때 인자의 수가 4개 이상인 것은 고려할 필요가 없다. 가장 작은 평균을 가지는 부분집합은 가장 작은 숫자를 포함한 2개 또는 3개의 인자만 생각하면 된다.

• 3개의 인자를 고려하는 것은 2개의 부분집합으로는 3개의 부분집합을 구할 수 없기 때문이다.

  • (2, 6, 1) = 3이고, (2, 6) = 4, (6, 1) = 3.5 일 때 (4, 3.5) = 3.75가 됨으로 3개의 경우는 따로 생각해야 한다.

2. Python

def solution(A):
    # write your code in Python 3.6
    
    min_value = sum(A[0:2])/2
    min_index = 0
    for i in range(len(A)):
        try:
            if min_value > (A[1+i] + A[i])/2:
                min_value = (A[1+i]+A[i])/2
                min_index = i
            
            if min_value > (A[2+i] + A[1+i] + A[i])/3:
                min_value = (A[2+i] + A[1+i] + A[i])/3
                min_index = i
        except:
            break
    
    return min_index