[Codility] Lesson 6 : NumberOfDiscIntersections - JAVA

문제

We draw N discs on a plane. The discs are numbered from 0 to N − 1. An array A of N non-negative integers, specifying the radiuses of the discs, is given. The J-th disc is drawn with its center at (J, 0) and radius A[J].
 
We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs have at least one common point (assuming that the discs contain their borders).
 
The figure below shows discs drawn for N = 6 and A as follows:
 
        A[0] = 1
        A[1] = 5
        A[2] = 2
        A[3] = 1
        A[4] = 4
        A[5] = 0
 
[문제 하단의 이미지 참고]
 
There are eleven (unordered) pairs of discs that intersect, namely:
 
discs 1 and 4 intersect, and both intersect with all the other discs;
disc 2 also intersects with discs 0 and 3.
Write a function:
 
        class Solution { public int solution(int[] A); }
 
that, given an array A describing N discs as explained above, returns the number of (unordered) pairs of intersecting discs. The function should return −1 if the number of intersecting pairs exceeds 10,000,000.
 
Given array A shown above, the function should return 11, as explained above.
 
Write an efficient algorithm for the following assumptions:
 
        - 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].
 
Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

solution(int[] A)에 입력되는 배열 A의 길이(N)는 0 ~ 100,000까지이고,
배열 A에는 0 ~ 2,147,483,647까지의 숫자가 들어갈 수 있다.

배열 A가 다음과 같이 주어질 때
        A[0] = 1
        A[1] = 5
        A[2] = 2
        A[3] = 1
        A[4] = 4
        A[5] = 0

A[0]은 인덱스 번호 0을 중심으로 하고 반지름이 1인 디스크를 의미한다.
A[1]은 인덱스 번호 1을 중심으로 하고 반지름이 5인 디스크를 의미한다.

이 때 서로 교차하는 디스크가 몇 개인지 계산하여 반환하면 된다.
(중복은 제외되는 듯 하다.)

예제에서 제시한 배열 A에는 디스크가 11번 교차하므로 11을 반환하면 된다.
단, 교차 횟수가 10,000,000을 초과하면 -1을 반환 해준다.

 

풀이 - 1

class Solution {
    public int solution(int[] A) {
        if(A.length < 2) return 0;
        int count = 0;
        for(int j=0; j<A.length-1; j++) {
            int discRadiuse = A[j];
            int discLeft = j - discRadiuse;
            int discRight = j + discRadiuse;
            for(int k=j+1; k<A.length; k++) {
                int compareLeft = k - A[k];
                int compareRight = k + A[k];
                if(discLeft > compareRight || discRight < compareLeft) continue;
                count++;
                if(count > 10000000) return -1;
            }
        }
        return count;
    }
}

 

'풀이 - 1'에 대한 회고

 

퍼포먼스는 나빠질 것이란 걸 알지만 이중 반복문을 이용했다.

먼저 인덱스 0번 디스크와 나머지 디스크를 비교한다.

이 때 인덱스 0번의 왼쪽 좌표(-1)보다 다른 디스크의 오른쪽 좌표가 작거나,

인덱스 0번의 오른쪽 좌표(1)보다 다른 디스크의 왼쪽 좌표가 크면 겹치지 않는다고 판단했다.

그리고 나머지의 경우에는 분명 겹친다고 생각했다.

 

 

그리고 결과를 확인했는데 정확도도 87%이다.

퍼포먼스야 0% 예상했는데 25%나 나오네?

 

 

반복문을 중첩하여 사용하기 때문에 최악의 경우 O(n*n)이 나올 것이라 예상했다.

그런데 어느 부분에서 정확하지 않았을까?

다른 사람은 어떻게 풀었는지 확인해봐야겠다.

 

다른 사람의 풀이

import java.util.Arrays;
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 
    }
}

 

'다른 사람의 풀이'를 통한 회고

 

다른 사람의 풀이를 설명하는데 조금 시간이 걸리기 때문에

일단 소스코드를 보면서 분석하길 바란다.

추후 소스코드의 알고리즘에 대해 설명을 작성할 예정!

 

 

결과는 정확도, 퍼포먼스가 100%이다.

정렬 알고리즘 파트라는 점을 고려해서 저런 알고리즘을 생각해낼 수 있도록

조금 더 경험을 쌓아야겠다.