JavaScript로 여러 배열에서 공통 요소(교집합) 구하는 방법

여러 개의 배열이 주어졌을 때, 모든 배열에 공통으로 존재하는 요소만 추출해야 하는 경우가 자주 있습니다. 이번 글에서는 임의의 개수의 배열을 인자로 받아, 모든 배열에 공통된 요소들로 이루어진 새로운 배열을 반환하는 JavaScript 함수를 작성해 보겠습니다. 만약 공통 요소가 하나도 없다면 빈 배열을 반환하면 됩니다.

문제 접근 방식

핵심 아이디어는 다음과 같습니다.

1. 두 배열의 교집합을 구하는 함수를 먼저 만듭니다.
2. 나머지 매개변수(rest parameter)를 활용해 여러 배열을 순차적으로 교집합 처리합니다.

구현 예제

const arr1 = [2, 6, 7, 1, 7, 8, 4, 3];
const arr2 = [5, , 7, 2, 2, 1, 3];
const arr3 = [1, 56, 345, 6, 54, 2, 68, 85, 3];

// 두 배열의 교집합을 구하는 함수
const intersection = (arr1, arr2) => {
   const res = [];
   for (let i = 0; i < arr1.length; i++) {
      if (!arr2.includes(arr1[i])) {
         continue;
      }
      res.push(arr1[i]);
   }
   return res;
};

// 임의의 개수의 배열에 대해 교집합을 구하는 함수
const intersectMany = (...arrs) => {
   let res = arrs[0].slice();
   for (let i = 1; i < arrs.length; i++) {
      res = intersection(res, arrs[i]);
   }
   return res;
};

console.log(intersectMany(arr1, arr2, arr3));

실행 결과

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

[2, 1, 3]

코드 설명

intersection 함수는 첫 번째 배열(arr1)의 요소를 하나씩 확인하면서, 해당 요소가 두 번째 배열(arr2)에 includes() 메서드로 존재하는지 검사합니다. 존재한다면 결과 배열에 추가하고, 없다면 continue로 건너뜁니다.

intersectMany 함수는 나머지 매개변수(...arrs)를 사용해 전달된 모든 배열을 하나의 배열로 묶습니다. 그런 다음 첫 번째 배열을 복사(slice())한 뒤, 나머지 배열들을 차례대로 intersection 함수에 적용하여 교집합을 점차 좁혀 나갑니다.

성능 개선 팁

배열의 크기가 클 경우 includes()는 매번 선형 탐색(O(n))을 수행하므로 비효율적일 수 있습니다. 이럴 때는 Set 객체를 활용하면 조회 속도를 O(1) 수준으로 개선할 수 있습니다.

const intersectMany = (...arrs) => {
   if (arrs.length === 0) return [];
   const sets = arrs.map(arr => new Set(arr));
   return [...sets[0]].filter(item =>
      sets.every(set => set.has(item))
   );
};

이처럼 상황에 맞는 방법을 선택하면 더 효율적인 코드를 작성할 수 있습니다.