Lesson 6. Sorting - NumberOfDiscIntersections #2 (속도 개선)

1. 속도 개선 아이디어

현재 모든 원을 하나씩 다 비교하고 있다. (전체탐색)

정렬을 이용하면, 비교 횟수를 줄일 수 있다.

 

예제를 정렬해보자.

정렬 기준은 왼쪽 값이다.

원점(index)	반지름(value)	왼쪽 값	오른쪽 값
1	5	-4	6
0	1	-1	1
2	2	0	4
4	4	0	8
3	1	2	4
5	0	5	5

 

정렬된 데이터를 가지고 비교해자.

왼쪽 값이 정렬되어 있으므로, 모든 원과 비교할 필요가 없다.

 

A[1]의 오른쪽 값보다 작거나 같은 왼쪽 값을 가지는 원 : A[0], A[2], A[4], A[3], A[5]

A[0]의 오른쪽 값보다 작거나 같은 왼쪽 값을 가지는 원 : A[2], A[4]

A[2]의 오른쪽 값보다 작거나 같은 왼쪽 값을 가지는 원 : A[4], A[3]

A[4]의 오른쪽 값보다 작거나 같은 왼쪽 값을 가지는 원 : A[3], A[5]

A[3]의 오른쪽 값보다 작거나 같은 왼쪽 값을 가지는 원 : 없음

A[5]의 오른쪽 값보다 작거나 같은 왼쪽 값을 가지는 원 : 없음(끝)

 

2. 코드 (C++)

#include <cstdint>
#include <algorithm>

int solution(vector<int> &A) {
 
    //왼쪽 값, 오른쪽 값을 pair로 저장한다
    vector<pair<int64_t, int64_t>> disc = {};

    for(size_t i = 0; i < A.size(); i++)
    {
        disc.emplace_back(pair<int64_t, int64_t>(i - A[i], i + A[i]));
    }

    sort(disc.begin(), disc.end());

    int cnt = 0;
    for(size_t i = 0; i < disc.size(); i++)
    {
        int64_t right_value = disc[i].second;
        for(size_t j = i + 1; j < disc.size(); j++)
        {
            if(disc[j].first <= right_value) cnt++;
            else break; //왼쪽 값이 더 크다면, 더 비교할 필요가 없다
        }

        if(cnt > 10000000) return -1;
    }

    return cnt;
}

 

3. 결과