[Codility][Sorting] NumberOfDiscIntersections 풀이 해석

코딜리티에서 나오는 문제는 보통 corner case만 잘 고려하면 어렵지 않은데

이 문제는 O(N)에 해결될 것 같은데 방법을 모르겠더라구요.

 

구글에서 검색해보면

github.com/Mickey0521/Codility/blob/master/NumberOfDiscIntersections.java

이 사람의 코드가 상당히 깔끔하고 좋은 것 같습니다.

 

class Solution {
    public int solution(int[] A) {
        
        // main idea:
        // 1. store all the "lower points" and "upper points" of the discs
        // 2. count the intersections (if one upper point > one lower point)
        
        // note: use "long" for big numbers (be careful)
        long[] lower = new long[A.length];
        long[] upper = new long[A.length];
        
        for(int i=0; i<A.length; i++){
            lower[i] = i - (long)A[i]; // note: lower = center - A[i]
            upper[i] = i + (long)A[i]; // note: upper = center + A[i]
        }
        
        // "sort" the "lower points" and "upper points"
        Arrays.sort(upper);
        Arrays.sort(lower);
        
        int intersection = 0; // number of intersections
        int j=0; // for the lower points
        
        // scan the upper points
        for(int i=0; i<A.length; i++){
        
            // for the curent "j" (lower point)
            while( j < A.length && upper[i] >= lower[j]){
                    intersection = intersection + j; // add j intersections
                    intersection = intersection - i; // minus "i" (avoid double count) 
                    j++;
            }          
        }
        
        // for the overflow cases
        if(intersection > 10_000_000)
            return -1;
        
        return intersection; // number of intersections      
    }
}

코드는 아주 심플합니다.

그런데 이해가 잘 되질 않더라구요. ㅎㅎ;;

 // scan the upper points
 for(int i=0; i<A.length; i++){

	// for the curent "j" (lower point)
	while( j < A.length && upper[i] >= lower[j]){
		intersection = intersection + j; // add j intersections
		intersection = intersection - i; // minus "i" (avoid double count) 
		j++;
	}          
}

x축 위에 놓인 각 원들의 왼쪽 점들과 오른쪽 점들을 오름차순으로 각각 정렬한 후에

오른쪽 점의 x좌표가 왼쪽 점의 x좌표와 같거나 더 큰 경우에 접점하는 경우로 봅니다. 말로 하면 설명이 좀 어려워지는데 위 코드를 보면 바로 이해가 될 거에요.

 

오름차순으로 정렬이 되어있고.. upper[i] >= lower[i]인 경우에 접점인 것은 쉽게 파악이 가능한데

 

intersection += j;

intersection -= i;

 

이 부분이 어렵습니다. j는 왼쪽 점을 나타내는 index, i는 오른쪽 점을 나타내는 index입니다.

왜 이렇게 해야하는지 한참을 생각했습니다.

 

무식하지만.. 길게 설명을 써보겠습니다.

 

하나하나 생각해봅시다.

upper[0]은 1입니다.

upper[0]보다 작거나 같은 값을 가지는 lower는 위 그림에서 보면 -4, -1, 0, 0 이렇게 4개인 것을 알 수 있습니다.

이 lower인 -4, -1, 0, 0인 원은 반드시 upper[0]인 원과 겹치게 되어있습니다.

왜냐하면 upper[0]보다 작은 upper는 없기 때문이죠. 그래서 -4, -1, 0, 0에서 시작한 원들은 upper[0]보다 큰 값을 upper로 가지게 되게 이것은 자명하게 원이 겹치는 것을 의미합니다.

그런데 -4, -1, 0, 0이 의미하는 원 4개 중에 하나는.. upper[0] 원을 포함합니다. 그래서 upper[0]을 빼야하므로 4-1을 하면 겹치는 원의 갯수인 3이 나옵니다.

 

upper[1]은 4입니다.(4로 끝나는 원이 2개가 있는데 순서는 중요하지 않습니다)

4보다 작거나 같은 값을 가지는 lower는 위 그림에서 보면 -4, -1, 0, 0, 2 이렇게 5개입니다.

-4, -1, 0, 0, 2가 의미하는 원이 upper[1]인 4인 원과 모두 겹칠까요?

그럴려면 -4, -1, 0, 0, 2가 의미하는 원의 upper가 모두 upper[1] 이상의 값을 가져야 합니다.

하지만 위그림에서 자세히 보면 5개 중에 4개는 그렇지만.. 나머지 1개 원은 그렇지 않습니다.

그 원은 바로.. upper[0] 원입니다. 이 원은 제외 시켜야 합니다.

그리고 upper[1] 본인 자신도 빼야 합니다.

따라서 upper[1]과 겹치는 원은 5-2=3 입니다.

upper[2]는 또 4입니다.

4보다 작거나 같은 값을 가지는 lower는 위 그림에서 보면 -4, -1, 0, 0, 2 이렇게 5개입니다.

-4, -1, 0, 0, 2가 의미하는 원이 upper[2]인 4인 원과 모두 겹칠까요?

그럴려면 -4, -1, 0, 0, 2가 의미하는 원의 upper가 모두 upper[2] 이상의 값을 가져야 합니다.

하지만 위그림에서 자세히 보면 5개 중에 4개는 그렇지만.. 나머지 1개 원(upper[0])은 그렇지 않습니다.

upper[2] 본인 자신도 빼야 합니다.

그리고 upper[2]와 upper[1]이 겹치는데 그건 바로 이전의 upper[1]을 계산할 때 고려됐기에 중복을 막기 위해 빼야 합니다.

따라서 upper[2]와 겹치는 원은 5-3=2 입니다.

 

upper[3]은 5입니다.

5보다 작거나 같은 값을 가지는 lower는 위 그림에서 보면 -4, -1, 0, 0, 2, 5 이렇게 6개입니다.

이 6개 중에서 2개만 겹칩니다.

upper[3] 본인을 빼야하며,

upper[0], upper[1], upper[2]도 빼야 합니다.

따라서 upper[3]과 겹치는 원은 6-4=2입니다.

upper[4]는 6입니다.

5보다 작거나 같은 값을 가지는 lower는 위 그림에서 보면 -4, -1, 0, 0, 2, 5 이렇게 6개입니다.

이 중에서 겹치는 원을 보면, 2개가 있으나 본인 자신을 빼면 1개만 겹칩니다. [0,8]원과 겹칩니다.

upper[0], upper[1], upper[2], upper[3]은 이전의 과정에서 중복처리 되었기 때문에 빼야합니다.

upper[4]는 본인이구요.

따라서 6-5=1입니다.

 

upper[5]는 8입니다.

8보다 작거나 같은 값을 가지는 lower는 -4, -1, 0, 0, 2, 5 이렇게 6개입니다.

위 그림을 보면 upper[5]가 가장 큰 값이라.. 겹치는 원이 없음을 쉽게 알 수 있습니다.

다르게 표현하면 upper[0], upper[1], upper[2], upper[3], upper[4], upper[5]를 빼주면

6-6=0입니다.

 

이렇게 하나하나 다 살펴보니 이해가 되네요.

 

intersection += j;

intersection -= i;

 

j를 더하는 것은.. upper[i]보다 작거나 같은 값을 가지는 lower의 갯수입니다. 이것이 의미하는 바는 upper[i]보다 더 작거나 같은 값을 가지는 lower들은 겹치는 원을 만들 가능성이 있어 더하는 것입니다. upper[i]보다 큰 lower들은.. 겹치는 원을 만들 수 없잖아요?

 

그리고 i를 빼는 것은 이전의 upper에서 구한 중복, 혹은.. upper[i]와 겹치지 않는 원을 제거하는 것입니다. j를 더하는 과정에서 이전에 구한 겹친 원이 중복으로 더해지거나, 겹치지 않은 원이 포함되기도 하므로.. i를 빼야 정확한 값이 나옵니다.

 

 

 

 

출처

github.com/Mickey0521/Codility/blob/master/NumberOfDiscIntersections.java

Mickey0521/Codility