Single Number

/LeetCode

문제 해석

요약

주어지는 정수의 배열에서 반복되지 않은 요소 찾기. 1개의 요소를 제외하고 나머지는 모두 반복된다.
시간복잡도는 O(n), 추가 메모리 없이 구현.

전문

🇰🇷 번역

비어있지 않은 정수의 배열이 주어지는데, 1개를 제외하고 모든 요소는 두번씩 나타난다. 그 하나인 요소를 찾아라.

주의:
너의 알고리즘은 선형시간복잡도를 가져야 한다. 그리고 추가 메모리 없이 구현할 수 있는가?

Input Output
[2,2,1] 1
[4,1,2,1,2] 4
🇺🇸 원문

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Input Output
[2,2,1] 1
[4,1,2,1,2] 4

🤔 문제 해결 방법 구상

  1. 선형시간복잡도는 O(n)으로 한번 순회시 나오는 복잡도

    • for문으로 nums를 돌면서 비교
  2. Set을 이용해보자.

    • Set은 자료형에 관계없이 유일한 값들을 객체안에 모으는 것이다. 간단히 말해 중복없는 쎄뚜쎄뚜를 만든다고 생각하면 된다.
    • 없으면 만들고, 있으면 지우는 과정을 통해 세트가 아닌것만 남게된다.

코드 구현

/**
 * @param {number[]} nums
 * @return {number}
 */
const singleNumber = function(nums) {
  let set = new Set();

  for (let i = 0; i < nums.length; i++) {
    if (!set.has(nums[i])) {
      set.add(nums[i]);
    } else {
      set.delete(nums[i]);
    }
  }

  return [...set][0];
};

결과 분석

Runtime: 72 ms
Memory Usage: 39.3 MB

시간복잡도 O(n), 공간복잡도도 O(n)이 나온다. 내가 생각한 방법인 Map, Set 등을 통한 hash table 방식은 모두 추가적으로 메모리를 사용하게 된다.

🧐 개선

Hash Table은 기본적으로 공간복잡도가 O(n)이 나온다. 추가 메모리를 사용하지 않는다는 조건을 만족시키려면, O(1)이 되어야 한다.

그래서 개인적으로 힌트로 사용하고 있는 Related Topics 항목을 살펴보았다. Related Topics항목에는 내가 사용한 Hash Table과 내가 생각한 방법이 아닌, Bit Manipulation이 있었다.

Bit Manipulation은 직역하면 비트 조작인데, 0과 1로 구성된 비트로 변환하고 비트연산자를 이용하여 계산하는 것을 말한다.
이 알고리즘은 비트연산자의 XOR을 사용하면 된다. XOR은 간단히 말해 비트로 변환한 결과를 자리수대로 비교하여 같으면 0, 다르면 1을 반환하고, 보여줄 땐 10진법 수로 보여준다.

간단히 예를 들면, 숫자 5과 6은 비트로 전환하면 0101, 0110이다. 전환된 각 자리값을 XOR로 비교하면 0011이고 3을 리턴한다.

XOR

5 ^ 6

비교하여 같으면 0을 반환한다는 것은, 같은 수가 있으면 결국 0을 반환한다는 것과 같다.

XOR

7 ^ 7

비교할 변수 하나만 설정해두고, 그 변수와 계속 누적비교하면 되기 때문에, 공간복잡도가 항상 일정한 O(1)이 나온다.

아예 추가적 변수 선언 없이 짧게 코드를 작성하고 싶다면, reduce로 가능하다.
리듀서는 간단히 말하자면 누적 계산이다. 배열의 각 요소에 대하여 함수를 실행하고 누적값은 반환한다.

개선 코드

  1. 모든 숫자를 XOR로 비교한다면, 같은 수가 있으면 0이 될 것이다.
  2. 누적비교 할 변수를 0으로 설정해두고,
  3. loop를 통해 하나씩 누적비교한 후 결과를 리턴
const singleNumber = function(nums) {
  let storage = 0;

  for (let i = 0; i < nums.length; i++) {
    storage ^= nums[i];
  }

  return storage;

reduce를 사용한 코드는 다음과 같다.

  1. 누적 비교는 reduce로 가능하다!
  2. 그렇다면, 리듀서의 콜백함수로 XOR을 이용하자.
const singleNumber = function(nums) {
  return nums.reduce((acc, cur) => acc ^ cur);
};

개선 결과

Runtime: 68 ms
Memory Usage: 34.1 MB

시간도 조금 개선되고, 메모리 사용량도 개선되었다.
시간복잡도는 O(n)을 유지하고, 공간복잡도는 O(1)로 개선할 수 있었다!

마무리

두번의 개선을 거쳐 코드를 짧게 변환시켰더니 뿌듯ㅎㅎ👽
그리고 비트연산자를 직접 사용하여 알고리즘을 푼 오늘의 경험으로, 풀이의 폭이 늘어날 것 같다. 그리고 비트연산자를 좀 더 자세히 공부하여 새롭게 포스팅해야겠다는 목표를 세우며 마무리!

Reference & Learn More

MDN Bitwise operators
MDN Set
MDN Reduce

Tags
Comments