(코딜리티) Lesson 5 : MinAvgTwoSlice - Python

문제 : app.codility.com/programmers/lessons/5-prefix_sums/min_avg_two_slice/

MinAvgTwoSlice coding task - Learn to Code - Codility

문제 해설

N개의 배열인 A일 때, P와 Q를 slice를 한 평균값이 가장 작은 시작 포인트를 구하시오.

 

예를 들어, A = [4, 2, 2, 5, 1, 5, 8]일 때,

slice (1, 2)일 때, (2+2) / 2 = 2

slice (3, 4)일 때, (5+1) / 2 = 3

slice (1, 4)일 때, (2+2+5+1) / 4 = 2.5

이다.

slice의 최소 평균 값의 시작포인트를 return하고,  만약 하나의 slice 이상일 경우 최소 평균일 때도 시작포인트를 return하면 된다.

제한 사항

N은 2~100,000사이의 값이다.

배열A의 각 요소는 -10,000 ~ 10,000 사이의 값이다

코드

def solution(A):
	
    prefix_sum = [0]
    s = 0
    # prefix sum을 위한 for문
    for i in A:
        s += i
        prefix_sum.append(s)
    
    m = float('inf')
    result = 0
    # j는 시작포인트로 처음부터 전체까지 for문
    for j in range(len(A)):
    	# 마지막 2개인 경우
        if j >= len(A)-2:
            for k in range(j+1, len(A)):
                r = (prefix_sum[k+1] - prefix_sum[j])/(k-j+1)

                if m > r :
                    m = r
                    result = j
        
        # slice 2개, 3개를 비교하기 위함
        else :    
            for k in range(j+1, j+3):
                r = (prefix_sum[k+1] - prefix_sum[j])/(k-j+1)

                if m > r :
                    m = r
                    result = j
                    
    return result

해설

평균의 작은 값은 최대 원소가 3개일 때까지 제일 작고 그이상으로는 작은값을 가질 수 없습니다.

따라서, 원소가 2~3개만 비교를 하면 됩니다.

그래서 if 문으로 마지막 2개만 비교하는 경우와 차레대로 2개 3개 비교하는 구문으로 2개로 나누었습니다.