[Codility] Lesson 6: Sorting - NumberOfDiscIntersections (javascript) 문제 풀이

깃허브 : https://github.com/miiingo/codility

Task description

원본 사이트 : app.codility.com/programmers/lessons/6-sorting/number_of_disc_intersections/

NumberOfDiscIntersections coding task - Learn to Code - Codility

- 평면에 N 개의 디스크를 그림
- 디스크는 0에서 N-1까지 번호가 매겨짐
- 디스크의 반경을 지정하는 N 개의 음이 아닌 정수의 배열 A가 제공됨
- J 번째 디스크는 중심이 (J, 0)이고 반경 A[J]로 그려짐
- J ≠ K이고 J 번째 및 K 번째 디스크에 하나 이상의 공통점이 있는 경우 J 번째 디스크와 K 번째 디스크가 교차한다고 함
- N 개의 디스크를 기술하는 배열 A가 주어지면, 교차 디스크(정렬되지 않은) 쌍의 수를 return
- 교차 디스크 쌍의 수가 10,000,000을 초과하면 함수는 -1을 return
- 가장 효율적인 알고리즘 작성
- N은 [0..100,000] 범위 내의 정수
- 배열 A의 각 요소는 [0..2,147,483,647] 범위의 정수

 

Solution

CASE 1: 왼쪽 끝점을 기준으로 정렬한 뒤, 개수 카운트 - 12%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const N = A.length;
    let array = new Array();
    let intersect = 0;
    
    for(let i=0; i<N; i++){
        let circle = {
            left: i - A[i],
            right: i + A[i]
        }
        array.push(circle);
    }
    array.sort((a, b) => a.left - b.left );
    
    for(let i=0; i<N-1; i++){
        for(let j=i+1; j<N; j++){
            if(intersect > 10000000){
                return -1;
            }
            if(array[j].left > array[i].right){
                break;
            }
            if(array[j].left == array[i].left || array[j].left < array[i].right){
                intersect++;
            }
        }
    }
    
    return intersect;
}

- array : 원의 양쪽 끝점(왼쪽, 오른쪽 끝점)을 가지고 있는 배열

- intersect : 교차하는 쌍의 개수

- array.left(원의 왼쪽 끝점)를 기준으로 배열 정렬
- 중복을 카운팅을 제거하기 위해 왼쪽부터 +1씩 증가시키며 탐색

- intersect가 10,000,000을 초과하면 -1을 return
- array.left를 기준으로 정렬한 상태에서 array[j].left가 array[i].right보다 크면, 이후의 모든 원들이 겹치지 않는다는 소리이므로 안쪽 for문 break
- array[j].left가 array[i].left와 같거나 array[j].left가 array[i].right보다 작으면 intersect 값 증가
=> intersect 값을 증가시키는 if문의 조건이 잘못됨

 

CASE 1: Result

 

CASE 1: Analysis

The following issues have been detected: wrong answers.
For example, for the input [1, 1, 1] the solution returned a wrong answer (got 2 expected 3).
다음과 같은 문제가 감지되었습니다. 오답.
예를 들어 입력 [1, 1, 1]의 경우 솔루션에서 잘못된 답변을 반환했습니다 (예상: 3, 결과 2).

 

CASE 2: if문 조건 수정 - 100%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const N = A.length;
    let array = new Array();
    let intersect = 0;
    
    for(let i=0; i<N; i++){
        let circle = {
            left: i - A[i],
            right: i + A[i]
        }
        array.push(circle);
    }
    array.sort((a, b) => a.left - b.left );
    
    for(let i=0; i<N-1; i++){
        for(let j=i+1; j<N; j++){
            if(intersect > 10000000){
                return -1;
            }
            if(array[j].left > array[i].right){
                break;
            }
            if(array[j].left >= array[i].left && array[j].left <= array[i].right){
                intersect++;
            }
        }
    }
    
    return intersect;
}

- CASE1에서 intersect 값을 증가시키는 if문의 조건을 수정
- array[j].left가 array[i].left보다 크거나 작고 array[i].right보다는 작거나 같을 경우 intersect 값 증가
   => 비교하는 원의 왼쪽 끝이 기준 원의 왼쪽 끝과 오른쪽 끝 사이에 포함되어있어야 함

 

CASE 2: Result

app.codility.com/demo/results/trainingQH7ZVW-6JP/

 

CASE 2: Analysis

The solution obtained perfect score.
이 솔루션은 완벽한 점수를 얻었습니다.

 

 

결론

이 문제를 풀기 위해 며칠을 고민했는지... 시도하다 포기하고, 다음날 다시 시도했다가 또 포기하고 계속 도전과 포기의 연속이었다.
구글링을 해서 다른 사람들의 코드를 봐도 도대체 무슨 소린지 이해가 되지 않았다.

이중 for문을 쓰면 성능이 나오지 않을 거라고 생각해서 계속 다른 방법을 찾아보다가, 결국 성능을 포기하고 정확성만 맞춰서 하고 다음에 다시 풀어봐야겠다... 라고 했는데, 100%가 나와서 놀랐다.

이중 for문을 쓴다고 무조건 성능이 안좋아지는 것은 아니고, if문으로 적절히 제어를 해주면 상관 없는 것 같다.
이래서 예외처리가 중요하다고 하는구나 새삼 깨닫게 되었다.


방법을 자세히 설명하자면 다음과 같다.
1. 배열 A의 왼쪽 끝점(left)과 오른쪽 끝점(right)에 대해 배열 array에 저장한다.

2. 배열 array의 left를 기준으로 오름차순 정렬한다.

3. array[0] ~ array[N-1]까지 각 항목을 기준으로 둔 상태에서 array[1] ~ array[N]이 기준 원에 겹치는지를 판단한다.
  1) intersect 값이 10,000,000을 초과하면 -1을 return
  2) 비교하는 원의 왼쪽 끝점(left)이 기준 원의 오른쪽 끝점(right)보다 크면 겹치지 않게 되므로 해당 기준 원에 대한 비교 중지
     -> 왼쪽 끝점(left)을 기준으로 정렬한 상태이기 때문에 이후의 원들도 기준 원과 겹치지 않음
  3) 비교하는 원의 왼쪽 끝점(left)이 기준 원의 왼쪽 끝점(left)과 오른쪽 끝점(right) 사이에 있으면 intersect 값을 증가

4. intersect 값을 return