[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