자바스크립트로 다차원 배열의 교집합 구하는 방법

리터럴 값으로 이루어진 여러 하위 배열을 담고 있는 다차원 배열이 주어졌을 때, 모든 하위 배열에 공통으로 등장하는 요소만 모아 교집합 배열을 반환하는 자바스크립트 함수를 작성해야 합니다.

문제 이해하기

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

const arr = [
  ["garden", "canons", "philips", "universal"],
  ["universal", "ola", "uber", "bangalore"]
];

두 하위 배열에 공통으로 존재하는 요소는 "universal" 하나뿐입니다. 따라서 함수는 이 값을 담은 배열을 반환해야 합니다.

Set 객체를 활용한 효율적인 접근 방법

교집합을 구할 때 가장 널리 쓰이는 전략은 다음과 같습니다.

• 첫 번째 하위 배열을 기준 배열로 삼습니다.
• 나머지 하위 배열들을 Set 객체로 변환해 요소 존재 여부를 빠르게 확인합니다.
• 기준 배열의 각 요소가 나머지 모든 Set에 포함된 경우만 결과 배열에 남깁니다.

예제 코드

const findMultiIntersection = (arr = []) => {
  // 입력이 비어 있으면 빈 배열 반환
  if (arr.length === 0) return [];

  const [first, ...rest] = arr;
  const restSets = rest.map(sub => new Set(sub));

  return first.filter(item =>
    restSets.every(set => set.has(item))
  );
};

console.log(findMultiIntersection(arr));

출력 결과

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

[ 'universal' ]

reduce와 filter를 사용한 대안

배열 내장 메서드인 reduce와 filter를 조합하면 코드를 더 간결하게 표현할 수도 있습니다.

const findMultiIntersection = (arr = []) =>
  arr.reduce((acc, cur) => acc.filter(item => cur.includes(item)));

console.log(findMultiIntersection(arr)); // [ 'universal' ]

다만 이 방식은 includes 메서드가 매번 선형 탐색을 수행하기 때문에, 데이터 양이 많아질수록 Set을 활용한 첫 번째 방법보다 성능이 떨어질 수 있습니다.

정리

다차원 배열의 교집합은 "첫 번째 배열을 기준으로, 해당 요소가 나머지 모든 배열에 존재하는지 검사한다"는 아이디어만 이해하면 어렵지 않게 구현할 수 있습니다. 데이터 크기가 클 경우에는 Set 객체를 활용해 조회 비용을 줄이는 것이 좋습니다.