[Codility] Prefix Sums - PassingCars 풀이
예문
https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/
A non-empty array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road.
Array A contains only 0s and/or 1s:
0 represents a car traveling east, 1 represents a car traveling west. The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the west.
For example, consider array A such that:
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).
Write a function:
class Solution { public int solution(int[] A); }
that, given a non-empty array A of N integers, returns the number of pairs of passing cars.
The function should return −1 if the number of pairs of passing cars exceeds 1,000,000,000.
For example, given:
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
the function should return 5, as explained above.
Write an efficient algorithm for the following assumptions:
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.
해석
- 배열 A : N개의 정수로 이루어짐
- A의 요소들은 도로상의 차들을 의미함.
- 0 : 동쪽으로 여행하는 차
- 1 : 서쪽으로 여행하는 차
- (P, Q) : P는 동쪽으로 여행하는 차, Q는 서쪽으로 여행하는 차
- 0 ≤ P < Q < N
- 지나가는 차의 짝의 수를 리턴하라!
풀이
- P보다 작은 값은 제외
- (동쪽으로 이동하는 차) * (그 이후에 서쪽으로 이동하는 차)
- ex) A[0] = 0, A[1] = 1, A[2] = 0, A[3] = 1, A[4] = 1
- A[0] 동쪽으로 이동 차량 + 1
- A[1] 동쪽으로 이동 차량 * 서쪽으로 이동하는 차 = 1 * 1 => 1
- A[2] 동쪽으로 이동 차량 + 1
- A[3] 동쪽으로 이동 차량 * 서쪽으로 이동하는 차 = 2 * 1 => 2
- A[4] 동쪽으로 이동 차량 * 서쪽으로 이동하는 차 = 2 * 1 => 2
- 총합 5
제약사항
- N의 범위는 정수 [1..100,000]
- A의 각 요소의 값은 0, 1 중의 하나를 가진다.
코드
public int solution(int[] A) {
int pCount = 0;
int sum = 0;
for (int i = 0; i < A.length; i++) {
if (0 == A[i]) pCount++;
else {
sum += pCount * A[i];
if (sum > 1000000000) return -1;
}
}
return sum;
}