[Codility] NumberOfDiscIntersections

NumberOfDiscIntersections coding task - Learn to Code - Codility

---

A = [1, 2]

  index를 중심으로, value를 반지름으로 하는 원을 그렸을 때 교차하는 원들의 쌍의 갯수를 구하는 문제이다. 예를 들어 A = [1, 2]라는 배열이 있다면 첫 번째 원은 0을 중심으로 1을 반지름으로 하는 주황색 원이다. 두 번째 원은 1을 중심으로 2를 반지름으로 하는 붉은색 원이된다. 이 둘은 겹쳐져있으므로 답은 1이 된다.

 

1. 풀이1 O(N^2)

원이 겹치는 2가지 경우의 수

  원이 겹치는 것은 2가지 경우가 있다. 첫 번째는 한 원이 다른 원을 포함하는 경우, 두 번째는 일부만 겹치는 경우이다. 이 때 특징은 한 원의 max가 다른 원의 min보다 크거나 같다는 점이다. 이를 이용하면 다음과 같은 코드를 작성할 수 있다. 

 

function solution(A) {
  let cnt = 0;
  const isOverlap = (c1, r1, c2, r2) => {
    let max1 = c1 + r1;
    let min2 = c2 - r2;

    if (max1 >= min2) return true;
    return false;
  }

  for (let i = 0; i < A.length - 1; i++) {
    for (let j = i + 1; j < A.length; j++) {
      if (isOverlap(i, A[i], j, A[j])) {
        cnt++;
      }
      if (cnt > 10000000) return -1;
    }
  }
  return cnt;
}

  위 코드는 답은 정확하지만, N의 최대값이 십만이므로, 제곱이 되면 시간을 초과하게 된다. 더 나은 방법을 찾아보자.

 

2. 풀이2

예시

  문제에서 주어진 예시를 그래프 상에 그려보면 위와 같다. 위에서 확인했듯이 두 원이 겹치는지 확인하기 위해선 원의 max, min 값만 필요하므로 선을 그리는 것으로도 충분하다.

 

  두 원 A, B의 겹치는가 확인할 때 필요한 것은 원 A의 max 값과 원 B의 min 값이다. 따라서 A의 min, B의 max는 의미가 없다. 예를 들어 1번 원과 겹치는 원을 찾을 때 min 값인 -4를 다른 값과 아무리 비교해도 의미가 없는 것과 같다.

 

  처음 코드에서 비효율적인 점은 일일이 모든 값을 비교한다는 점이다. 모든 값을 비교하지 않으려면 정렬을 이용하면 된다. 예를 들어 정렬된 배열 A = [1, 2, 3, 4] 와 B = [2, 3, 4, 5]가 있을 때 A의 첫번째 요소 1과 B의 첫번째 요소 2만 비교해도 B의 모든 요소가 기준인 A의 첫번째 요소 1보다 크다는 것을 알 수 있는 것과 같다. 

 

  문제에서 필요한 것은 원의 max 값과 min 값이다. 따라서 이 값들만 가져와서 정렬시켜놓고 비교해나간다면 좀 더 효율적인 비교를 할 수 있을 것이다.

 

 

정렬 결과

  max 값과 min 값을 정렬하면 위와 같다. 이 상태에서 겹치는 쌍을 찾아보자. x축을 왼쪽부터 보는게 편하므로  min_Array순으로 원들을 순서대로 놓아가면서 비교할 것이다.

 

 

모든 원은 1 이상의 max 값을 가지므로 지금 놓여진 모든 원은 겹칠 것이다.

  처음 놓여진 원(-4)은 쌍을 이룰 수 없으므로 디스크 쌍의 변화는 없다.

  새로운 원(-1)이 추가되었을 때 먼저 max_Array를 이용하여 범위를 초과하는 원이 있는지 확인한다. 즉, min인 -1과 max인 1을 비교하는 것이다. min < max 이므로, 모든 원이 -1보다 더 큰 지점에서 끝난다는 것을 알 수 있다. 즉, 지금까지 놓여진 원 A(-4)와 원 B(-1)은 언제 끝나는지 정확히 알 수 없지만, 적어도 1 이상의 지점에서 끝나므로(max) 두 원은 겹치는 원이 맞다.

(지금 보니 A와 B가 반대로 되어있다... 하지만 문제풀이에 큰 지장은 없으므로 일단 그대로 두겠다..)

 

 

모든 원은 1 이상의 max 값을 가지므로 지금 놓여진 모든 원은 겹칠 것이다.

  세번째 원(0)이 추가되었을 때도 마찬가지이다. 놓여져 있는 모든 원이 적어도 1까지의 지점에서 끝나므로 모든 원이 겹치고 있는 상황이다. 이 때 (A, B)는 이전 단계에서 찾은 쌍이므로, (A, C)와 (B, C) 총 2개만 새롭게 찾은 쌍의 갯수로 추가해주자. 네번째 원도 min이 0이므로 같은 상황이 반복된다.

 

 

범위를 벗어나는 원이 발생

  다섯번째 원에서 새로운 상황이 생긴다. 다섯번째 원이 1이상의 min을 갖는 원. 즉, 지금까지의 X~1 사이의 범위를 벗어난 원이 발생한 것이다. 이 상황은 지금까지처럼 'A~E원이 모두 겹치는 건 아니다'를 의미한다. 겹치지 않는 원을 알 수 있을까? 이 때는 max_Array를 이용하면 힌트를 얻을 수 있다. max_Array의 인덱스를 +1해보자

 

 

1개의 원은 범위를 벗어난다.

  max_Array의 인덱스가 1이 되어 4를 가리키게 되었다. 이는 모든 원 중에서 한 가지(max=1) 빼고는 max가 4이상을 갖는다는 의미이다. 그렇다면 max = 1인 원이 이전까지 놓인 원 중에 있는지만 확인하고 그 안에 있다면 새롭게 추가되는쌍은 3개가 될 것이다.(원래 A,B,C,D 모두와 쌍을 지어 4여야 하는데 그 중 하나가 겹치지 않기 때문에 3이된 것이다.)

 

  그런데 생각해보면 max = 1인 원은 이전까지 놓인 원 중 하나일 수 밖에 없다. 지금까지 놓이지 않은 원은 min을 2이상 갖기 때문에 max가 2 미만인 1을 가질 수 없기 때문이다. 즉, 이전까지 놓인 A, B, C, D 중 하나가 1에서 끝났고, 새롭게 발견된 쌍은 3이 된다. 단, A, B, C, D 중 어떤 원이 끝났는지는 알 수 없으며, 중요하지도 않다. 겹치는 순서쌍을 구하는 것이 아니라 순서쌍의 갯수를 구하는 문제이기 때문이다.

 

 

3개의 원은 범위를 벗어난다.

  임의로 A가 1에서 끝났다치고 마지막 원을 올려보자. 마지막 원에서도 다섯번째 원과 동일하게 범위를 벗어나는 원이 생기므로 동일한 과정을 수행한다. 단, 문제에서 한 점이라도 겹치면 겹친다고 판정하기 때문에 max와 min이 동일한 값을 가리킬 때도 겹친다고 판정한다. 따라서 원래 끝나지 않은 B, C, D, E와 쌍을 지어야 하지만 2개의 원이 4에서 끝나므로 2개의 원만 겹쳐진다.

 

  최종적으로 각 과정에서 0 + 1 + 2 + 3 + 3 + 2 = 11 이라는 답이 나온다.

 

3. 코드

function solution(A) {
  const maxArr = [];
  const minArr = [];
  for (let i = 0; i < A.length; i++) {
    maxArr.push(i + A[i]);
    minArr.push(i - A[i]);
  }

  maxArr.sort((a, b) => a - b); // 퀵소트 NLogN
  minArr.sort((a, b) => a - b);

  let cnt = 0;
  let disk = 0;
  let maxIdx = 0;
  for (let minIdx = 0; minIdx < minArr.length; minIdx++) {
    // 1. 새로운 원을 놓았을 때 범위에서 빠지는 디스크가 있을 수 있다.
    while (maxArr[maxIdx] < minArr[minIdx]) {
      disk--;
      maxIdx++;
    }
    
    // 2. 새로운 디스크 쌍을 센다.
    cnt += disk;

    // 2-1. 범위를 초과하면 return -1
    if (cnt > 10000000) return -1;

    // 3. 범위에 놓여있는 디스크에 추가한다.
    disk++;
  }
  return cnt;
}