NumberOfDiscIntersections (Codility)

문제

N개의 배열에 각 디스크의 반지름 크기 값이 들어 간다. 그리고 0 ~ N-1 까지의 인덱스 범위가 디스크의 위치가 된다. 디스크끼리 서로 교차하는 경우 그것을 한 쌍으로 본다. 이러한 쌍이 몇개 있는지 구하는 문제이다.

 

해결 방법

우선 처음으로 시도했던 방법은 각 디스크 별로 순회하며 다른 디스크끼리 서로 교차하는지 검사한 후, Heap에 집어넣어 중복값을 배제하고 Heap 크기만큼 출력하는 방법이다. 하지만 디스크를 검사할때마다 그 디스크를 제외한 모든 디스크를 검사하기 때문에(이중 반복문) O(N^2)의 시간 복잡도가 나왔다.

 

이 방법은 역시 효율성이 안좋기 때문에 통과할 수 없었다. 최소 O(NlogN)이하는 되어야 통과가 가능하다. 

 

위 예제에 있는 디스크들의 모양을 다음과 같이 표식화 시켜보았다.

 

디스크의 범위의 시작점을 lower, 끝점을 upper라고 부르겠다. 이제 이 디스크를 lower를 기준으로 정렬하면 다음과 같다.

 

이제 가장 처음에 나온 lower값을 가진 디스크 A부터 쌍을 구해보자. -4에서 아직 디스크가 A 하나 이므로 교차하는 쌍은 0이다. 이제 -1에서 또 다른 디스크 B를 만나게 된다. 이미 A가 있으므로 한쌍이 교차하게 된다. A와 B를 추가하여 현재 교차되는 디스크의 수는 2개이다.

 

이제 0에서 디스크 C를 만나게 되었다. 이미 디스크 A, B가 있으므로, (A, C), (B, C)로 교차가 된다. 총 교차하는 쌍은 기존 1쌍 + 존재하는 디스크의 수 2개 = 3쌍이 된다. B를 추가하여 현재 교차되는 디스크의 수는 3개이다.

 

0에는 디스크 D도 존재한다. 디스크 A, B, C가 있으므로, (A, D), (B, D), (C, D)로 교차한다. 그래서 총 교차하는 쌍은 3쌍 + 3개 = 6쌍이 된다. D를 추가하여 현재 교차되는 디스크의 수는 4개이다.

 

2에서 E를 만나기 전에 B의 디스크가 upper를 만나 범위를 넘어가게 된다. 그래서 디스크의 수를 4개에서 3개로 줄여줘야 한다. E를 만나면 A, C, D가 교차하므로 6쌍 + 3개 = 9쌍이 된다. E를 추가하여 디스크 수는 4개가 된다.

 

5에서 디스크 F를 만나기 전에, C, E 디스크가 upper를 만나 범위를 벗어난다. 그러므로 C, E를 뺀 교차되는 디스크의 수는 2개이다. 그러므로 F 디스크에서 교차될 수 있는 디스크는 A와 D 디스크이다. 교차되는 쌍은 9쌍 + 2개 =  11쌍이 된다.

 

모든 디스크를 살펴봤으므로 총 교차하는 디스크의 쌍은 11쌍이다.

 

코드로 표현하면 다음과 같다.

 

주의할 점이 하나 있는데, 범위가 int의 최대값까지 이므로 lower, upper에 들어가는 값은 int의 범위를 넘어간다. 그렇기 때문에 long long 값으로 넣어줘야 알맞은 값이 들어간다.

#include <algorithm>

int solution(vector<int>& A) {
	int result = 0;
	vector<long long> upper, lower;
	for (int i = 0; i < A.size(); ++i) {
		lower.push_back((long long)i - A[i]);
		upper.push_back((long long)i + A[i]);
	}
	sort(lower.begin(), lower.end()); // lower를 구하고 오름차순 정렬
	sort(upper.begin(), upper.end()); // upper를 구하고 오름차순 정렬

	int count = 0; // 교차되는 디스크를 세기 위한 변수
	int idx_upper = 0; // 현재 upper의 위치를 알기 위함
	for (const auto iter : lower)
	{
		// 교차 검사를 하기 전에 범위를 벗어난 디스크는 제외시킨다.
		while (iter > upper[idx_upper])
		{
			--count;
			++idx_upper;
		}
		// 교차하는 쌍을 센다.
		result += count;
		++count;
		if (result > 10000000) return -1;
	}
	return result;
}