Lesson 5. Perfix Sums - PassingCars #3 (속도 개선-2)

1. 속도 개선 아이디어

예제를 다시 분석해보자. 

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

 

A[0]이 마주치는 차량과  A[2]가 마주치는 차량이 일부 겹친다.

이유는 A[2]가 마주치는 차량은, A[0]도 마주치기 때문이다.

즉, 차량을 각각 짝지을 필요 없이, 1을 만날 때마다, 앞에있는 0의 갯수만큼 더해주면 된다.

 

A[0]         ↔  A[1]이 마주치는 차량 1대

A[0]/A[2]  ↔  A[3]이 마주치는 차량 2대

A[0]/A[2]  ↔  A[4]이 마주치는 차량 2대

 

 

2. 코드 (C++)

int solution(vector<int> &A) {

    int cnt = 0;
    int east_cars = 0;
    for(size_t i = 0; i < A.size(); i++)
    {
        if(A[i] == 0) east_cars++; //동쪽으로 여행하는 차량 수
        else cnt += east_cars;

        if(cnt > 1000000000) return -1;
    }

    return cnt;
}

 

 

3. 결과