Lesson5. Prefix Sums - PassingCars

PassingCars - Count the number of passing cars on the road.

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

문제요약

N개의 정수 배열 A, A는 0 or 1의 값을 갖고 0은 동쪽으로 1은 서쪽으로 이동하는 차를 의미한다. 0 <= P < Q < N이고 P는 동쪽, Q는 서쪽으로 이동한다고 할 때 (P,Q)는 서로 지나치게 되는데 이렇게 서로 지나치는 차의 쌍의 수를 계산.

1,000,000,000을 초과하는 경우는 -1 반환

Assume that:

N is an integer within the range [1..100,000];

each element of array A is an integer that can have one of the following values: 0, 1.

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(1) (not counting the storage required for input arguments).

풀이

0인 항목의 오른쪽에 있는 1의 수를 구해서 모두 더하면 된다.(반대로 1보다 왼쪽에 있는 0의 수도 가능), O(N)안에 계산을 하려면 이전 결과를 저장하면 된다.

즉 [0,1,0,1]이라고 하면 오른쪽 붙 1의 수를 세어가면서 0을 만날 때 마다 현재까지 1의 수를 누적해서 더해주면 된다. [2]의 0을 만나면 이전까지 1은 1개이고, [0]의 0을 만나면 이전까지 1은 2개이므로 1+2가 되어 지나치는 차의 쌍은 총 3개가 된다.