Codility Lesson6 - NumberOfDiscIntersections

🔍 문제

---

 

NumberOfDiscIntersections coding task - Learn to Code - Codility

 

✏️ 풀이 - JS

---

처음 주어진 배열 A로 원을 그린다. 배열 인덱스가 중심점, 반지름은 배열의 값이다. 원을 그렸을 때 겹치는 원의 개수를 구하면 된다. 이번에도 역시나 나는 이중 for문에서 헤어나오지 못했다... 아래와 같이 풀어서 정확도는 100%지만 역시나 performance에서는 62%가 나와서 총 81%가 나왔다. 시간복잡도는 N(N**2)😓

일단 논리는 처음 배열 A에서 index를 기준으로 원 그리기의 startPoint와 endPoint를 구한다. 그리고 나서 시작점이 가장 왼쪽에있는 원부터 차례대로 정렬해준다. 가장 왼쪽의 원부터 차례로 자신의 원과 겹치는 원이 있는지 확인 후 intersectionCnt++ 해주었다.

function solution(A) {
    let intersectionCnt = 0;
    let pointArr = A.map((radius, i) => [i-radius, i+radius]); //시작점, 끝점 배열

    pointArr.sort((a, b) => a[0] - b[0]); //가장 왼쪽에 있는 원부터 정렬

    for(let i = 0; i < A.length-1; i++) {
        let baseEnd = pointArr[i][1];

        for(let j = i+1; j < A.length; j++) {

            if(pointArr[j][0] <= baseEnd) {
                intersectionCnt++;
                if(intersectionCnt > 100000000) return -1;
            }
        }
    }

    return intersectionCnt;

}

이렇게 풀고나서 자고일어나서 다시 보는데 아직 모르겠다ㅎㅎㅎ추후 다시 도전 해볼 예정