[Codility] (Lesson6 | Sorting) NumberOfDiscIntersections - JavaScript

문제

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:

function solution(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].

문제해석

배열 A는 x축 위에 원들을 정리해 놓은 것이라고 생각하면 될 것 같다. 배열 A의 index는 원의 중심축, 값은 반지름이다. 배열 A의 내용을 토대로 x축에 원을 그렸을 때 겹치는 원의 갯수를 구하는 내용이다. 겹치는 갯수가 10,000,000개를 넘긴다면 -1을 리턴하고 그 이하라면 갯수를 리턴하면 된다.

문제풀이

• 배열 A에 해당하는 반지름을 가지고 원의 양 끝을 구한 배열을 map을 통해 만든다. 중심축이 인덱스 값이기 때문에 원의 왼쪽 값은 인덱스 값 - 반지름, 오른쪽 값은 인덱스 + 반지름이 된다.
• sort를 이용해 왼쪽값이 같지 않다면 왼쪽값을 기준으로 오름차순으로 정렬하고, 같다면 오른쪽값을 기준으로 내림차순하여 정렬한다.
  • 이러한 정렬은 왼쪽 원부터 비교하고, 왼쪽 값이 같은 원이라면 더 큰 원 먼저 비교한다는 뜻이 된다.
• 겹치는 원을 찾는 것이기 때문에 기준이 되는 원 arr[i]와 비교하는 원 arr[j]는 arr[j]의 왼쪽 값이 arr[i]의 왼쪽 값보다는 크고 오른쪽 값보다는 작은지 확인해서 기준이 되는 원 안에 비교하는 원이 있다는 것을 알아낸다.
• 겹치는 원의 개수를 더하고 10,000,000보다 크다면 -1을 리턴하고, 겹치지 않을때는 break를 통해 효율성을 높여준다.

코드

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let answer = 0;
    let arr = A.map((v,i)=>[i-v,i+v]);
    arr.sort((a,b)=>{
        if(a[0]!==b[0]) return a[0]-b[0]
        else return b[1]-a[1]
    });

    for(let i = 0; i<arr.length; i++){
        for(let j = i+1; j<arr.length; j++){
            if(arr[i][0] <= arr[j][0] && arr[i][1] >= arr[j][0]) answer++
            else break;
            if(answer>10000000) return answer = -1
        }
    }
    
    return answer
}

최종결과

출처

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