[Javascript] Codility Lesson 6 - NumberOfDiscIntersections

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

 

문제 요약:

• 겹치는 원이 총 몇 쌍인지 구해야한다.
• 원의 반지름을 나타내는 정수를 요소로 갖는 배열 A가 주어진다.
• 배열 A의 길이 범위는 [1... 100000] 이다.
• 배열 A의 각 요소 범위는 [0..2147483647] 이다.
• 겹치는 원의 쌍이 10,000,000를 초과하면 -1를 반환한다.

function solution(A) {
    let result = 0;
    let discsList = A.map((radius, point) => {
        return [point - radius, point + radius]
    });

    discsList.sort((a, b) =>  a[0] - b[0]);

    for(let i = 0; i < discsList.length; i++) {
        if (result > 10000000) {
            result = -1;
            break;
        };

        let endPoint = discsList[i][1];

        for(let j = i+1; j < discsList.length; j++) {
            let startPoint = discsList[j][0];
            
            if (endPoint >= startPoint) {
                result++;
            } else {
                break;
            }
        }
    }

    return result;
}

https://app.codility.com

배열 A를 통해 원의 시작점과 끝점으로 이루어진 배열을 요소로 갖는 배열을 생성한 뒤, 원의 시작점을 기준으로 오름차순 정렬을 한다.  i번째 원과 i + 1번째 원이 겹치는지에 대한 여부는 (i번째 원의 끝 점) >= (i + 1번째 원의 시작점) 으로 판단하면 되고, 시작점을 기준으로 오름차순 정렬했기 때문에 (i번째 원의 끝 점) < (i + 1번째 원의 시작점)이 되는 순간 그 다음 원들은 체크할 필요가 없으므로 다음 턴으로 넘어간다. (cf: 시간 복잡도는 O(N*log(N)) or O(N))