[codility] PassingCars

app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/

PassingCars coding task - Learn to Code - Codility

01011에서 두개를 뽑아서 (0,1)을 만드는데 0은 항상 1보다 작아야 함

01011을 반대로 뒤집으면 11010이고 

0이 나올 때까지 1의 개수를 세어주면 된다

 

왜냐하면 0 앞에 1이 몇개나 있는지 개수를 세는거니까

첫번째 0은 2개, 두번째 0은 3개라서 총 5개가 됨

 

0이 나올때까지 1의 개수를 저장해두는 게 count one 이고

0이 나와서 이전 partial sum값과 count one을 더해주는 게 partial sum이고

partial sum과 이전 전체 합을 더해주는게 total sum으로 하면 끝!

 

첫번째 0이 나왔을 때 

partial sum = 2

total sum = 2

 

두번째 0이 나왔을 때

partial sum = 2+1

total sum = 2+(2+1)

 

def solution(A):
    # write your code in Python 3.6
    p_sum = 0
    t_sum = 0
    count_one = 0
    for i in range(len(A)-1,-1,-1):
        if A[i] == 0:
            p_sum += count_one
            t_sum += p_sum
            count_one = 0
        else:
            count_one +=1
        if t_sum > 1000000000:
            return -1
    return t_sum