Codility - Passing Cars // C++

문제

 

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:

int solution(vector<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.

 

크기 N의 벡터 A가 주어진다. A는 0과 1로만 이루어져 있으며 0은 동쪽으로 가는 차를, 1은 서쪽으로 가는 차를 의미한다.

 

이 때, 서로 마주치는 차의 대수를 구하시오.(1,000,000,000이 넘을 경우에는 -1을 리턴)

 

---

 

풀이

 

문제를 푸는 것보다 이해가 안 되서 시간을 더 잡아먹었던 것 같다....

 

서로 마주치는 경우의 수는 배열의 두 요소를 비교할 때, 왼쪽에 0이 있고 오른쪽에 1이 있는 경우를 모두 합하면 된다.

 

이것도 단순하게 이중 for문을 사용하면 시간 초과가 되기 때문에 배열의 마지막부터 해당 인덱스까지의 1이 나오는 개수를 더한 배열을 선언하여 합을 구하였다.

---

 

코드

int solution(vector<int> &A) {
    vector<int> sum(A.size());
    
    int count = 0;
    
    for(int i=A.size()-1;i>=0;i--){ // i+1 ~ A의 크기까지 1이 나온 횟수
        sum[i] = count;
        
        if(A[i] == 1) // 자기 자신은 포함하지 않음
            count++;
    }
    
    count = 0;
    for(int i=0;i<A.size();i++){
        if(A[i] == 0){ // 0인 경우에만 1인 차와 마주침
            count += sum[i];
        }
       
        if(count > 1000000000)
            return -1;
    }
    return count;
}