[1, 3, 17, 3, 1]

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

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)

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

</aside>

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)