[Python] 5.3. MinAvgTwoSlice

https://app.codility.com/programmers/lessons/5-prefix_sums/

5. Prefix Sums lesson - Learn to Code - Codility

---

1차 시도

Task Score 50%

Correctness 100%

Performance 0%

시간복잡도 O(N ** 3)

def solution(A):

    N = len(A)
    prefix_sum = [A.copy() for _ in range(N)]
    min_val = 10 ** 10
    answer = N

    for p in range(N):
        for q in range(p+1,N):
            if p < q:
                prefix_sum[p][q] = prefix_sum[p][q-1] + A[q]
                avg = prefix_sum[p][q]/(q-p+1)
                if avg < min_val:
                    min_val = avg
                    answer = p
                elif avg == min_val:
                    answer = min(answer, p)

    return answer