Lesson 5. Perfix Sums - PassingCars #1

1. 문제

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.

서로 마주치는 차량의 수를 세는 문제. (동쪽으로 여행하는 차는 0 / 서쪽으로 여행하는 차 1)

예) return 5

vector A	마주치는 차량
A[0] = 0	A[1], A[3], A[4]
A[1] = 1
A[2] = 0	A[3], A[4]
A[3] = 1
A[4] = 1

 

 

2. 매개변수 조건

• vector A 크기 : 1 ~ 100,000
• vector A 요소 값 : 0 or 1

 

3. 풀이 전략

• 동쪽으로 여행하는 차와 서쪽으로 여행하는 차를 각각 분리해서 저장한다. (0과 1을 분리)
• 서쪽으로 여행하는 차(1)를 내림차순으로 정렬한다.
• 그 후, 마주칠 수 있는 차량을 센다.

 

4. 주의사항

• 마주치는 차량이 1,000,000,000을 초과하면 -1을 return해야 한다.

 

5. 코드 (C++)

#include <algorithm>

int solution(vector<int> &A) {

    // 0 과 1 분리
    vector<int> east = {}; //0
    vector<int> west = {}; //1
    for(size_t i = 0; i < A.size(); i++)
    {
    	//A의 index 저장
        if(A[i] == 0) east.emplace_back(i);
        else west.emplace_back(i);
    }

    // index 내림차순 정렬
    sort(west.begin(), west.end(), greater<int>());

    //마주치는 차량 세기, east[i] < west[i]
    int cnt = 0;
    for(size_t i = 0; i < east.size(); i++)
    {
        for(size_t j = 0; j < west.size(); j++)
        {
            if(east[i] > west[j]) break; //west는 내림차순 정렬이 되어있으므로, break
            cnt++;
            if(cnt > 1000000000) return -1;
        }
    }

    return cnt;
}

 

 

6. 결과