Lesson6. Sorting - NumberOfDiscIntersections

NumberOfDiscIntersections - Compute the number of intersections in a sequence of discs.

https://app.codility.com/programmers/lessons/6-sorting/number_of_disc_intersections/

문제요약

0부터 N-1까지 N개의 disc를 평면에 그린다. N개의 음이 아닌 정수 배열 A는 disc의 반지름을 나타내고 j번째 disc는 (j,0)을 중심으로 반지름 A[j]으로 그려진다. J와 K가 같지 않고 J번째 disc와 K번째 disc가 최소 한 점이상의 공통 point를 가질 때 intersect하다고 한다.

A에서 intersect하는 disc 쌍의 갯수를 반환하고, 쌍의 수가 10,000,000을 초과하면 -1을 반환한다.

Assume that:

N is an integer within the range [0..100,000];

each element of array A is an integer within the range [0..2,147,483,647].

Complexity:

expected worst-case time complexity is O(N*log(N));

expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

풀이

특정 원을 기준으로 겹침을 판단하는 방법은, 현재 끝점보다 오른쪽에 끝점이 위치하고 시작점이 현재 시작점보다 왼쪽에 위치한 원들을 찾으면 된다. 즉, 현재 원의 끝점이 다른 원의 사이에 포함되는지를 확인한다.(시작점을 기준으로 해도 마찬가지)

이를 빠르게 확인하기 위해서는 끝점을 오름차순 정렬을 하면 판단하려는 끝점을 기준으로 오른쪽에 있는 끝점들은 모두 오른쪽에 위치하므로, 시작점에 대해서만 현재 끝점보다 왼쪽에 위치하는지를 확인하면 되는데, 마찬가지로 이를 위해서 시작점도 오름차순으로 정렬하고 binary search를 이용하면 O(log(N))시간에 확인이 가능하다.

즉 시작점과 끝점을 정렬하고, 끝점 각각에 대해서 끝점보다 작거나 같은 시작점의 수를 구하고 여기에 자기자신과 이미 전에 판단한 끝점의 수를 빼주면 각 끝점에 대한 겹치는 원의 수를 구할 수 있다.

이전에 판단한 끝점의 수를 항상 빼주는 이유,
시작점은 끝점보다 항상 작거나 같다는 사실이 당연하지만 이해하는데 도움이 된다. 여기에 끝점을 오름차순으로 정렬해서 검사하고 있다는 사실을 조합하면 현재 검사중인 끝점에 매칭되는 시작점들은 당연히 현재 끝점보다 작거나 같게 되어 있다. (start1 <= end1, end1 <= end2면 start1 <= end2)
즉 현재 끝점 보다 작거나 같은 시작점의 갯수를 구하게 되면 여기엔 아직 검사하지 않은 끝점들과 매칭되는 시작점의 수 + 나 자신(같은 이유) + 이전에 검사한 끝점 수가 나오게 된다. 그렇기 때문에 -1 - i가 필요하다.