[ Codility 코딜리티 ] Lesson 5 PassingCars Python 파이썬 풀이

 

// 문제 요약

 

동쪽으로 가는 차량을 0,

서쪽으로 가는 차량을 1 이라고 할때

N개의 1과 0으로 구성된 A중에서

지나간 차량의 수를 구해라

 

단 지나간 차량이란

0 <= P < Q < N일때

A[P] = 0, A[Q] = 1인 경우를 말한다.

 

// 문제 풀이

 

왜 저런 경우를 passing으로 정의하는지는 

정말로 잘 모르겠지만

머리를 비우고 문제를 풀도록 하자.

 

 

먼저 풀이로는 스택이 떠오른다.

하지만 

이런식으로 연속되지 않더라도

임의의 P와 Q를 모두 만족해야 하므로

스택은 여기서 올바른 풀이라 할 수 없다.

 

정통 prefix sums 알고리즘을 통해서 풀어보도록 하자.

 

코드부터 보자.

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

def solution(A):
    # write your code in Python 3.6

    cumulated, summ = [0], 0
    for n in A:
        summ += n
        cumulated.append(summ)

    passing_cars = 0
    for i, n in enumerate(A):
        if not n:
            passing_cars += summ - cumulated[i + 1]
            if passing_cars > 1e9:
                return -1
    return passing_cars

P가 반드시 Q보다 작고

A[P]가 반드시 0이어야하는 점을 근거로

A[P] == 0 이면 P 이후의 모든 1의 개수를 리턴해라

라는 문제로 볼 수 있다.

 

여기서는 친절하게도

0과 1로 값을 주기 때문에

군더더기 없이 깔끔하게 풀 수 있다.