Codility - MinAvgTwoSlice [Python]

 문제

 

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

MinAvgTwoSlice coding task - Learn to Code - Codility

 

 

 

 

 

 문제 상황

 

- 주어진 리스트를 순회하며 부분 집합의 평균 중 최소가 되는 경우의 시작 인덱스를 출력한다.

 

 

 

 

 

 해결 전략

 

- 수학적 지식이 필요한 문제이다. 어떤 두 수의 평균은 항상 작은 수보다 크고 큰 수보다 작다. 즉, 서로 다른 두 수 a, b(a<b) 가 있을 때, 평균인 (a+b)/2 는 a<(a+b)/2<b 가 된다. 서로 다른 4개의 수가 존재할 때(a<b<c<d)에는 a,b,c,d의 평균 (a+b+c+d)/4가 작은 두 수의 평균 (a+b)/2보다 크고, (c+d)/2 보다 작다. 

 

pf) (a+b+c+d)/4, (a+b)/2, (c+d)/2 가 있을 때, 모든 요소에 4를 곱해주면 (a+b+c+d), (a+b)*2,(c+d)*2가 된다. 이 때, 1번 요소와 2번요소를 비교하면 (a+b+c+d) > (a+b+a+b)가 된다((c+d)> (a+b)) 마찬가지로 1번요소와 3번요소를 비교하면 (c+d)*2가 더 크므로 (a+b)/2 < (a+b+c+d)/4 < (c+d)/2 가 된다. .

 

- 요소 a,b,c (a<b<c) 가 있을 때, (a+b)/2, (a+b+c)/3, (b+c)/2의 요소에 6을 곱하면, (a+b)*3, (a+b+c)*2, (b+c)*3이 된다. 1번 요소와 2번요소를 비교하면 a+b, 2*c가 된다. 이 경우, c가 a+b의 평균보다 크면 오른쪽이 더 크고, 아니면 왼쪽이 더 크므로 대소가 결정되었다고 할 수 없다. 그래서 길이가 3인 요소도 확인할 필요가 있다.

 

 

 

 

 

 코드

 

def solution(A):
    min_avg = 10001
    min_idx = -1
    for i in range(len(A)-1):
        if sum(A[i:i+2])/2 < min_avg :
            min_avg = sum(A[i:i+2])/2
            min_idx = i
        if i != len(A)-2 and sum(A[i:i+3])/3 < min_avg :
            min_avg = sum(A[i:i+3])/3
            min_idx = i
    return min_idx
 
 
# efficiency test failed
def solution(A):
    c_sum = [0]*(len(A)+1) # cumulative sum
    for i in range(1, len(c_sum)):
        c_sum[i] = c_sum[i-1] + A[i-1]
    min_avg = float('inf')
    min_index = 0
    for i in range(1,len(c_sum)):
        for j in range(i):
            temp_avg = (c_sum[i]-c_sum[j])/i-j
            if temp_avg < min_avg : 
                min_avg =temp_avg
                min_index = j
    return j

 

 

 

 

 

 해설

 

- 최소인 평균은 항상 부분집합의 길이가 2 또는 3일 경우에 발생하므로 순회하며 길이 2,3으로 슬라이싱해 평균을 계산하면 최대 3*N의 시간만큼 소요되므로 O(N)으로 순회 가능하다.

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 알고리즘 문제지만 수학 문제에 가까운 문제였다. dp 등 알고리즘의 해법으로만 접근하려고 하였는데 수학적 지식을 요구하는 문제도 있다는 사실을 알았다.