JavaScript로 세로 구간 집합에서 모든 분리된 교차 구간 찾기

문제 개요

이 글에서 다룰 문제는 y1(시작점)과 y2(끝점) 좌표로 정의되는 여러 개의 세로 구간(vertical regions)이 주어졌을 때, 일정 길이 이상으로 겹치는 구간들을 모두 찾아내는 것입니다.

좌표계의 원점은 화면의 왼쪽 상단에 위치하므로, y2 값은 항상 y1보다 큽니다.

예를 들어 다음과 같은 구간 배열이 있다고 가정해 보겠습니다.

const regions = [
   [10, 100],
   [50, 120],
   [60, 180],
   [140, 220]
];

요구 사항

우리는 이러한 구간 배열을 첫 번째 인수로, 숫자를 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 두 번째 인수로 지정된 크기(예: 20 단위)보다 큰, 서로 분리된(disjointed) 교차 구간을 모두 찾아 반환해야 합니다.

위 예제 배열에서 길이 기준을 20 단위로 설정하면, 기대하는 출력 결과는 다음과 같습니다.

const output = [
   [60, 100],
   [140, 180]
];

접근 방식

이 문제는 단순화된 알고리즘으로 해결할 수 있습니다. 먼저 모든 구간 쌍을 순회하며 서로 겹치는 항목을 탐색하고, 겹치는 부분의 공통 구간을 계산한 뒤, 아직 처리되지 않은 매칭만 필터링하여 결과에 추가하는 방식입니다.

핵심 로직은 두 구간의 교집합을 구할 때 시작점은 두 시작점 중 더 큰 값(Math.max)으로, 끝점은 두 끝점 중 더 작은 값(Math.min)으로 설정하는 것입니다. 계산된 시작점이 끝점보다 작다면 실제로 겹치는 구간이 존재한다는 의미이며, 해당 구간은 'used' 플래그로 표시해 중복 처리를 방지합니다.

예제 코드

이를 구현한 전체 코드는 다음과 같습니다.

const regions = [
   [10, 100],
   [50, 120],
   [60, 180],
   [140, 220]
];
const getIntersections = (arr,num) => {
   let disjoint, res;
   return arr.reduce((acc,val,ind,array) => {
      if (val.used){
         return acc;
      };
      res = array.map((el, index) => array[(ind + index) % array.length]) .reduce((s,e) => {
         disjoint = [Math.max(s[0],e[0]), Math.min(s[1],e[1])];
         return disjoint[0] < disjoint[1] ? (e.used = true, disjoint) : s;
      });
      res[1] - res[0] > num && acc.push(res);
      return acc;
   },[]);
}
console.log(getIntersections(regions, 20));

실행 결과

코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

[ [ 60, 100 ], [ 140, 180 ] ]

결과를 살펴보면 [60, 100]은 [50, 120]과 [60, 180] 구간이 겹치는 부분이며, [140, 180]은 [60, 180]과 [140, 220] 구간이 겹치는 부분입니다. 두 교차 구간 모두 지정한 최소 길이인 20 단위를 충족하므로 정상적으로 결과에 포함되었습니다.