JavaScript로 두 배열 사이의 누락된 숫자 찾는 방법

문제 설명

두 개의 배열 arr1과 arr2를 인수로 받는 JavaScript 함수를 작성해야 합니다.

arr2는 arr1의 모든 요소를 포함하되 순서만 무작위로 섞인 복사본이며, 단 하나의 요소가 빠져 있습니다.

따라서 우리가 만들 함수는 바로 이 누락된 요소 하나를 찾아 반환해야 합니다.

접근 방법

두 배열을 정렬한 뒤 한 요소씩 비교하는 방법도 가능하지만, 정렬 과정 때문에 시간 복잡도가 O(n log n)까지 늘어납니다. 또한 합계나 XOR을 이용한 방식은 중복 값이 없을 때만 유효합니다. 이 문제처럼 중복 요소(예: 두 개의 6)가 존재하는 경우에는 해시 객체를 활용한 빈도 카운팅이 가장 안정적이고 효율적인 선택입니다.

예제 코드

const arr1 = [6, 1, 3, 6, 8, 2];
const arr2 = [3, 6, 6, 1, 2];

const findMissing = (arr1 = [], arr2 = []) => {
   // 1단계: arr1의 각 숫자별 등장 횟수를 객체에 기록
   const obj = {};
   for (let i = 0; i < arr1.length; i++) {
      if (obj[arr1[i]] === undefined) {
         obj[arr1[i]] = 1;
      } else {
         obj[arr1[i]]++;
      }
   }

   // 2단계: arr2를 순회하며 카운트를 하나씩 차감
   for (let i = 0; i < arr2.length; i++) {
      if (obj[arr2[i]] === undefined || obj[arr2[i]]-- === 0) {
         return arr2[i];
      }
   }

   // 3단계: 카운트가 남아 있는 숫자가 곧 누락된 숫자
   for (key in obj) {
      if (obj[key] > 0) {
         return Number(key);
      }
   }
   return -1;
};

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

출력 결과

콘솔에는 다음과 같이 출력됩니다.

8

코드 동작 원리

이 알고리즘은 세 단계로 구성됩니다.

첫 번째 루프에서는 arr1의 모든 요소를 순회하면서 각 숫자가 몇 번 등장했는지 객체(obj)에 기록합니다. 위 예제에서는 { 6: 2, 1: 1, 3: 1, 8: 1, 2: 1 } 형태의 빈도표가 만들어집니다.

두 번째 루프에서는 arr2를 순회하며 해당 숫자의 카운트를 하나씩 차감합니다. 만약 arr2에 arr1에 없는 값이 들어 있거나 특정 숫자의 카운트가 이미 0이 된 경우에는 즉시 그 값을 반환하는 방어 로직도 포함되어 있습니다.

세 번째 루프에서는 여전히 카운트가 0보다 큰 숫자를 찾습니다. arr2에는 없어서 차감되지 않고 남아 있는 숫자, 즉 위 예제에서는 8이 바로 누락된 숫자입니다.

복잡도 분석

각 배열을 한 번씩만 순회하므로 시간 복잡도는 O(n), 빈도를 저장하기 위한 객체가 필요하므로 공간 복잡도 역시 O(n)입니다. 정렬 기반 접근(O(n log n))보다 빠르며, 중복 값이 있어도 정확하게 동작한다는 장점이 있습니다.