JavaScript 배열에서 일치하는 숫자 쌍 개수 구하기

이번 글에서는 중복된 값이 포함될 수 있는 정수 배열을 입력받아, 동일한 숫자로 만들 수 있는 쌍(pair)의 개수를 구하는 JavaScript 함수를 작성해 보겠습니다.

예를 들어, 입력 배열이 다음과 같다고 가정해 봅시다.

const arr = [1, 5, 2, 1, 6, 2, 2, 9];

그렇다면 기대하는 출력 결과는 다음과 같습니다.

const output = 2;

그 이유는 이 배열에서 만들 수 있는 쌍이 (1, 1)과 (2, 2), 딱 두 개이기 때문입니다. 참고로 2는 세 개가 있지만, 이미 짝을 이룬 값은 다시 사용할 수 없으므로 하나의 쌍으로만 계산됩니다.

문제 해결 접근 방식

가장 간단하고 직관적인 방법은 다음과 같습니다.

1. 원본 배열을 변경하지 않도록 얕은 복사(shallow copy)를 만든다.
2. 복사한 배열을 오름차순으로 정렬한다.
3. 정렬된 배열을 순회하며 인접한 두 요소가 같으면 하나의 쌍으로 카운트하고, 해당 요소들을 건너뛴다.

구현 예제

위 로직을 구현한 코드는 다음과 같습니다.

const arr = [1, 5, 2, 1, 6, 2, 2, 9];
const countPairs = (arr = []) => {
    const { length } = arr;
    let count = 0;
    // 얕은 복사를 통해 원본 배열이 변경되지 않도록 함
    const copy = arr.slice();
    copy.sort((a, b) => a - b);
    for(let i = 0; i < length; i++){
       if(copy[i] === copy[i + 1]){
          i++;
          count++;
       };
   };
   return count;
};
console.log(countPairs(arr));

코드 설명

배열을 오름차순으로 정렬하면 동일한 값들이 서로 붙어 있게 됩니다. 따라서 반복문에서 현재 요소 copy[i]와 바로 다음 요소 copy[i + 1]만 비교하면 됩니다. 두 값이 일치하면 카운트를 1 증가시키고 i++로 해당 값을 건너뛰어, 같은 값이 세 개 이상 있더라도 중복 계산되지 않도록 처리합니다.

출력 결과

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

2

이처럼 정렬과 인접 요소 비교만으로 반복 값의 쌍 개수를 효율적으로 구할 수 있습니다. 시간 복잡도는 정렬이 지배하므로 O(n log n)이며, 추가 배열 없이 원본을 정렬해도 된다면 메모리를 더 절약할 수 있습니다.