JavaScript로 두 배열 간의 대칭 차집합 구하기

대칭 차집합(Symmetric Difference)이란?

수학에서 두 집합 A와 B의 대칭 차집합은 A △ B로 표기합니다. 이는 A 또는 B 어느 한쪽에는 속하지만, 두 집합 모두에는 속하지 않는 원소들의 집합으로 정의됩니다.

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

const A = [1, 2, 3, 4, 5, 6, 7, 8];
const B = [1, 3, 5, 6, 7, 8, 9];

두 배열에서 공통으로 존재하는 값은 1, 3, 5, 6, 7, 8입니다. 따라서 한쪽에만 존재하는 원소들만 남기면 A와 B의 대칭 차집합은 다음과 같습니다.

const diff = [2, 4, 9]

구현 예제

다음은 두 배열의 대칭 차집합을 구하는 자바스크립트 코드입니다.

const A = [1, 2, 3, 4, 5, 6, 7, 8];
const B = [1, 3, 5, 6, 7, 8, 9];

const symmetricDifference = (arr1, arr2) => {
  const res = [];
  for(let i = 0; i < arr1.length; i++){
    if(arr2.indexOf(arr1[i]) !== -1){
      continue;
    }
    res.push(arr1[i]);
  }
  for(let i = 0; i < arr2.length; i++){
    if(arr1.indexOf(arr2[i]) !== -1){
      continue;
    }
    res.push(arr2[i]);
  }
  return res;
};

console.log(symmetricDifference(A, B));

코드 동작 방식

이 함수는 두 단계로 동작합니다.

첫 번째 반복문에서는 첫 번째 배열(arr1)의 각 요소를 순회하면서, 해당 요소가 두 번째 배열(arr2)에도 존재하면 건너뛰고(continue), 존재하지 않을 경우에만 결과 배열에 추가합니다.

두 번째 반복문에서는 반대로 두 번째 배열(arr2)의 요소 중 첫 번째 배열(arr1)에 없는 값만 결과 배열에 추가합니다. 그 결과, 양쪽 중 한 곳에만 존재하는 원소들만 최종 배열에 담기게 됩니다.

실행 결과

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

[2, 4, 9]

참고: Set을 활용한 성능 개선

indexOf는 배열을 처음부터 끝까지 탐색하기 때문에 시간 복잡도가 O(n)입니다. 따라서 위 방식은 전체적으로 O(n²)의 비용이 발생할 수 있습니다. 데이터 크기가 클 경우 Set을 사용해 조회 시간을 O(1)로 줄이는 것이 좋습니다.

const symmetricDifference = (arr1, arr2) => {
  const setA = new Set(arr1);
  const setB = new Set(arr2);
  return [
    ...arr1.filter(x => !setB.has(x)),
    ...arr2.filter(x => !setA.has(x))
  ];
};

이 방식은 동일한 결과를 반환하면서도 대용량 데이터에서 훨씬 빠르게 동작합니다.