[코딜리티] NumberOfDiscIntersections (JavaScript)

 

문제 출처

문제 요약

원의 시작점과 반지름이 배열로 주어질때 서로 겹치는 쌍의 개수를 구하는 문제.

배열의 index 가 시작점 원소값이 반지름이다.

문제 풀이

function solution(A) {
  let result = 0;
  const discs = A.map((n, i) => [i - n, i + n]);
  discs.forEach(([min, max]) => {
    result +=
      discs.filter(([cmin, cmax]) => cmin <= max && cmax >= min).length - 1;
  });
  return result / 2;
}

• 원의 최소값과 최대값 좌표를 가지고 있는 배열 discs 를 만든다.
• 해당 배열을 루프 돌려서 겹치는 것들의 개수를 구한다.
• 자기 자신을 제외하기 위해 -1 쌍의 개수 이기 때문에 2로 나눠준다.
• 당연히 퍼포먼스에서 꽝

function solution(A) {
  let result = 0;
  const discs = A.map((n, i) => [i - n, i + n]);
  const copys = discs.slice();
  discs.forEach(([min, max]) => {
    copys.shift();
    result += copys.filter(([cmin, cmax]) => cmin <= max && cmax >= min).length;
  });
  return result;
}

• 자기 자신을 제외하고 중복 순회를 피하기 위해 비교용 배열을 만들고 한번 순회 할때마다 첫번쨰 요소를 제거한다.
• 퍼포먼스에서 위 문제와 동일한 점수

function solution(A) {
  let result = 0;
  const discs = A.map((n, i) => [i - n, i + n]);
  discs.sort((a, b) => a[0] - b[0]);
  const copys = [...discs];
  discs.forEach(([min, max]) => {
    copys.shift();
    result += copys.filter(([cmin, cmax]) => cmin <= max).length;
  });
  if (result >= 10000000) {
    return -1;
  }
  return result;
}

• 구글링을 통해서 sort를 추가 했다.
• 결과는 위와 동일 😭

function solution(A) {
  let result = 0;
  const discs = A.map((n, i) => [i - n, i + n]);

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

  discs.forEach(([min, max], j) => {
    for (let i = j + 1; i < A.length; i++) {
      if (discs[i][0] <= max) {
        ++result;
      } else {
        break;
      }
      if (result > 10000000) return -1;
    }
  });

  return result;
}

• sort해서 겹치는 않는 원부터는 루프를 돌릴필요가 없어서 break 추가했다.
• 퍼포먼스가 상승했으나 100%는 아님

최종

function solution(A) {
  let result = 0;
  const discs = A.map((n, i) => [i - n, i + n]);

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

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

  return result;
}

• forEach 를 for문으로 변경 했을 뿐인데 퍼포먼스 100% 🤔

결론

1. 2중 for 문이어도 break 만 잘써도 알고리즘 복잡도를 낮출 수 있다니...
2. 언듯 보면 forEach 보다 for 문이 더 연산이 빨라 보이지만 일반적인 상황은 아니다. 기본적으로는 forEach 를 사용하는게 좋을듯.