[코딜리티] passing cars (python)

O(n) 시간에 풀어야하는 문제이다 

0 일 경우 현재 차의 개수 cur을 +1해주며 1을 만날 경우 현재까지 있던 왼쪽에 있던 차의 개수를 전체 sum에다 더하면 된다.

왼쪽에 있는 0의 개수가 1이 만나게 될 차의 개수이기 때문이다.

 

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    sum=0
    cur=0
    for i,car in enumerate(A):
        # print(i,cur)
        if car==0:
            cur+=1
        else:
            sum+=cur
    if sum>1000000000:
        return -1
    else: return sum

o(n^2)는 효율성 통과를 못하지만 A[i+1:].count(1) 이런식으로 구한 다음 sum에다 더해주면 된다