[Algorithm] 자바스크립트 쌍(pairs)을 포함하는 배열에서 유니크 넘버 찾기

아래 배열에서 단 한번만 나열되는 유니크 숫자는 17이다. 1과 3은 쌍을 이루고 있기 때문에 두번씩 나열되고 있다. 이런 배열에서 유니크 넘버(17)만 찾아내려면 어떻게 해야할까?

[1, 3, 17, 3, 1]

 

Naive Solution — O(n*n)

---

2중 for문을 사용한 예시. 모든 숫자를 한번씩 돌아가면서 검사해야 되기 때문에 O(n*n)의 시간복잡도를 갖는다. 배열 길이가 5라면 정답을 찾을 때까지 최대 25번의 순회가 이뤄질 수도 있다.

function singleNumber(nums) {
  for (let i = 0; i < nums.length; i++) {
    let found = false;

    for (let j = 0; j < nums.length; j++) {
      if (nums[j] === nums[i] && i !== j) {
        found = true;
        break;
      }
    }

    if (!found) return nums[i];
  }
}

 

Linear Solution — O(n)

---

💡 O(n)은 알고리즘 실행 시간이 선형이 되는 것을 뜻한다. 선형 시간(Linear time; 线性时间)이란 배열 길이(n)와 비례하는 만큼의 알고리즘 실행 시간이 필요한 것을 말한다.

 

memo 객체를 이용해 2번 이상 등장한 숫자를 기억하는 방법. for 문을 돌면서 처음 나오는 숫자를 key로 지정하여 값을 1로 초기화하고, 이미 등장했던 숫자가 또 나온다면 1을 더한다. 모든 순회를 마친 후 memo 객체에 값을 1로 갖는 key는 한 번만 등장했던 유니크 숫자다.

 

아래 코드는 nums 숫자만큼 순회하므로 시간복잡도는 O(n)이 된다.

function findUniqueNumber(nums) {
  const memo = {};

  for (let i = 0; i < nums.length; i++) {
    const num = nums[i];
    memo[num] = (memo[num] || 1) + 1;
  }

  // memo -> { '1': 2, '3': 2, '17': 1 }
  return Object.keys(memo).reduce((unique, num) => {
    return memo[num] === 1 ? Number(num) : unique;
  }, NaN);
}

 

Bitwise XOR Solution — O(n)

---

자바스크립트는 기본적으로 10진수 단위로 작업을 처리하지만 비트 연산자를 이용하면 2진수도 처리 할 수 있다. XOR ^ 연산자는 비교하는 2개의 비트가 서로 다르면 1, 같으면 0를 반환한다 — 비트 연산자 참고(한글)

10 ^ 12; // 6
// 1010 (10)
// 1100 (12)
// ----
// 0110 (6) -> 1과1 같아서 0, 0과1 달라서1, 1과0 달라서 1, 0과0 같아서 0

 

같은 숫자 2개를 XOR ^ 연산으로 비교하면 항상 0이 나온다.

4 ^ 4 // 0;
// 100 (4의 이진수)
// 100
// ---
// 000 (2진수 000은 10진수 0)

 

마찬가지로 쌍(pairs)을 포함하는 배열에서, 각 요소에 한번씩 XOR 연산을 수행하면 결과는 항상 0이 된다. 동일한 짝을 가진 숫자들이 짝을 이뤄 연산돼서 결과적으로 0이 나오는 것. XOR 연산자는 교환법칙(숫자 위치를 바꿔도 결과가 변하지 않는 성질)과 결합법칙(연산 순서를 바꿔도 결과가 변하지 않는 성질)을 만족하기 때문에 순서와 상관없이 항상 동일한 값이 나온다. 즉, [1, 1, 3, 3]이든 [3, 1, 3, 1]이든 배열의 숫자들이 모두 짝을 이룬다면 결과는 항상 0으로 동일하다.

[1, 3, 1, 3].reduce((val, num) => {
  console.log(
    `val: ${val}(${val.toString(2)}), num: ${num}(${num.toString(
      2,
    )}), val^num: ${val ^ num}(${(val ^ num).toString(2)})`,
  );

  return val ^ num;
});

// 괄호안은 2진수
// val: 1(1), num: 3(11), val^num: 2(10)
// val: 2(10), num: 1(1), val^num: 3(11)
// val: 3(11), num: 3(11), val^num: 0(0)

 

쌍을 포함하는 배열에 유니크 숫자(17)를 추가하면, 결과는 항상 이 유니크 숫자가 된다. 유사한 쌍(1, 3) 요소는 서로를 상쇄(抵消)하기 때문에, 모든 숫자에 대해 XOR 연산을 수행하면 결국 고유한 값을 갖는 숫자(17)만 남게 된다. XOR 연산에서 순서는 상관없기 때문에 유니크 숫자가 배열 어디에 위치하든 결과는 항상 같다.

[1, 3, 17, 1, 3].reduce((val, num) => {
  console.log(
    `val: ${val}(${val.toString(2)}), num: ${num}(${num.toString(
      2,
    )}), val^num: ${val ^ num}(${(val ^ num).toString(2)})`,
  );

  return val ^ num;
});

// 괄호안은 2진수
// val: 1(1), num: 3(11), val^num: 2(10)
// val: 2(10), num: 17(10001), val^num: 19(10011)
// val: 19(10011), num: 1(1), val^num: 18(10010)
// val: 18(10010), num: 3(11), val^num: 17(10001)

 

이처럼 XOR 연산을 이용해 아래처럼 깔끔하게 한 줄로 작성할 수 있다. 비트 수준에서의 평가가 일반적인 논리연산자보다 빠르기 때문에 반복할 요소가 많을 수록 비트 연산이 더 효율적이다.

function findUniqueNumber(nums) {
  return nums.reduce((val, num) => val ^ num);
}

 

번외 — XOR 연산자 규칙

---

a ^ b를 이용해 얻은 값이 c라면 a b c는 항상 한 쌍(pairs)이 되는 규칙이 있다. 이 한 쌍에서 임의로 2개를 골라 XOR 연산을 수행하면 결과는 항상 한 쌍 중 나머지 값이 나온다. — 참고글

let a = 3;
let b = 5;
let c = a ^ b; // 6

a ^ c; // 5 (b의 값)
b ^ c; // 3 (a의 값)

 

레퍼런스

---

How to find a unique number in a list containing pairs? - Yonatan Kra  

 

---

글 수정사항은 노션 페이지에 가장 빠르게 반영됩니다. 링크를 참고해 주세요