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

1. 이전 코드 분석

마주치는 차량을 셀 때, 하나하나 직접 세고 있다.

 

 

2. 속도 개선 아이디어

하나씩 직접 세지 말고, 산술 연산을 하면 좀 더 빠르게 처리할 수 있다.

 

 

3. 코드 (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);
    }

    //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]) //오름차순으로 되어 있으므로, 이후 모든 차량은 마주한다
            {
                cnt += west.size() - j; //마주치는 차량 수 계산
                if(cnt > 1000000000) return -1;
                else break;
            }
        }
    }

    return cnt;
}

 

 

4. 결과