[Python] 5.4. PassingCars

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

5. Prefix Sums lesson - Learn to Code - Codility

---

Task Score

100%

Correctness

100%

Performance

100%

시간복잡도

O(N)

def solution(A):

    east = []

    for i in range(len(A)):
        if A[i] == 0:
            east.append(i)
            
    if len(east) == 0:
        return 0

    prefix_sum = []
    for i in range(len(east)-1):
        prefix_sum.append(east[i+1]-east[i]-1)
    
    if east[-1] != len(A):
        prefix_sum.append(len(A)-1-east[-1])

    cnt =  0
    for i in range(len(prefix_sum)):
        cnt += prefix_sum[i]*(i+1)
        if cnt > 10 ** 9:
            return -1

    return cnt