[Codility] PassingCars

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.

A의 각 인덱스는 i 칸에서 출발하는 차를 뜻하고 A[i] 의 값은 진행하는 방향을 뜻한다.

여기서 서로 교차하는 차의 수는 0 이후에 1이 나올 경우 혹은 1 왼쪽의 0의 갯수를 모두 세는 알고리즘을 짜야한다. 문제를 O(N)으로 풀기 위해서 0의 갯수를 세는 cntZero 가 있고 1이 나올때마다 1의 왼쪽에 있는 0 의 총갯수를 sum 해주었다.

즉, 0 이후의 1 갯수를 셀때는 O(N^2) 인 반면 1 이전의 0 갯수를 세면 O(N)으로 짤 수 있다.

class Solution {
    public int solution(int[] A) {
        
        int cntZero = 0;
        int cnt = 0;
        
        for(int i = 0; i < A.length; i++){
            if(A[i] == 0){
                cntZero++;
            }
            else if(A[i] == 1){
                cnt += cntZero;
                if(cnt > 1000000000){
                    return -1;
                }
            }
        }
        return cnt;
    }
}