자바스크립트로 다차원 배열과 단일 배열의 교집합 찾기 — 하위 배열별 공통 요소 추출 함수

이번 글에서는 숫자로 구성된 2차원 배열을 첫 번째 인자로, 단일 숫자 배열을 두 번째 인자로 받는 자바스크립트 함수를 작성해 보겠습니다. 이 함수는 첫 번째 인자로 전달된 각 하위 배열을 검사하여, 두 번째 배열과 공통으로 포함된 요소들만 골라 새로운 하위 배열을 만든 뒤 이들을 하나의 배열로 묶어 반환합니다.

예를 들어 입력이 다음과 같다고 가정해 보겠습니다.

입력 예시

const arr1 = [
  [1, 2, 5, 6],
  [5, 13, 7, 8],
  [9, 11, 13, 15],
  [13, 14, 15, 16],
  [1, 9, 11, 12]
];
const arr2 = [9, 11, 13, 15, 1, 2, 5, 6];

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.

[
  [1, 2, 5, 6],
  [5, 13],
  [9, 11, 13, 15],
  [13, 15],
  [1, 9, 11]
]

출력 배열의 첫 번째 하위 배열은 첫 번째 인자 배열의 첫 번째 하위 배열과 두 번째 배열 사이의 공통 요소들로 구성됩니다. 마찬가지로 두 번째 하위 배열은 두 번째 하위 배열과 두 번째 배열의 공통 요소들이 되며, 나머지 하위 배열도 같은 방식으로 처리됩니다.

Set 객체를 활용한 구현

교집합을 구할 때 가장 효율적이고 가독성이 좋은 방법은 Set 객체를 활용하는 것입니다. Set은 해시 기반으로 구현되어 있어 특정 값의 포함 여부를 상수 시간(O(1))에 확인할 수 있기 때문입니다.

const arr1 = [
  [1, 2, 5, 6],
  [5, 13, 7, 8],
  [9, 11, 13, 15],
  [13, 14, 15, 16],
  [1, 9, 11, 12]
];
const arr2 = [9, 11, 13, 15, 1, 2, 5, 6];

const findIntersection = (arr1 = [], arr2 = []) => {
  // 두 번째 배열을 Set으로 변환하여 조회 속도 향상
  const lookup = new Set(arr2);

  // 각 하위 배열에서 두 번째 배열에 포함된 요소만 필터링
  return arr1.map((subArray) =>
    subArray.filter((num) => lookup.has(num))
  );
};

console.log(findIntersection(arr1, arr2));

코드 설명

• new Set(arr2) : 두 번째 배열을 Set 객체로 변환합니다. 이렇게 하면 각 요소의 존재 여부를 반복문 없이 빠르게 확인할 수 있습니다.
• map() : 첫 번째 인자로 받은 2차원 배열의 각 하위 배열을 순회하며 새로운 배열을 만듭니다.
• filter() : 각 하위 배열에서 lookup(Set)에 존재하는 숫자만 남겨 교집합을 형성합니다.

이 방식의 전체 시간 복잡도는 하위 배열의 요소 수를 n, 두 번째 배열의 크기를 m이라 할 때 O(n + m) 수준으로, 중첩 반복문을 사용하는 O(n × m) 방식보다 훨씬 효율적입니다.

간단한 대안 : includes() 사용

배열 크기가 작고 성능이 중요하지 않은 경우에는 Set 없이 Array.prototype.includes()만으로도 동일한 결과를 얻을 수 있습니다.

const findIntersection = (arr1, arr2) =>
  arr1.map((subArray) => subArray.filter((num) => arr2.includes(num)));

다만 includes()는 내부적으로 선형 탐색을 수행하므로 데이터가 커질수록 Set을 사용하는 첫 번째 방법이 유리합니다.