[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