Missing Number

/LeetCode

문제 해석

요약

0부터 n까지 정수가 포함된 배열이 주어지는데, 누락된 숫자 하나를 구하여라.
가능하다면 시간복잡도는 O(n), 공간복잡도는 O(1)을 갖도록 하라.

전문

🇰🇷 번역

0, 1, 2, ..., n에서 가져온 n개의 고유숫자를 포함한 배열이 주어지면, 그 배열에서 누락된 숫자 하나를 찾으시오.

Input Output
[3,0,1] 2
[9,6,4,2,3,5,7,0,1] 8

주의:
너의 알고리즘은 선형 시간복잡도를 가져야한다. 상수 공간복잡도만 추가하여 구현할 수 있나?

🇺🇸 원문

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Input Output
[3,0,1] 2
[9,6,4,2,3,5,7,0,1] 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

🤔 문제 해결 방법 구상

이 문제는 Single Number와 비슷한 문제이다.

그때와 비슷하게 비트연산자를 이용하면 될 것 같다.

  1. 배열이 주어지고, 그 배열의 길이 + 1의 값이 정수의 끝 수라고 할 수 있다.
  2. for문을 돌면서 0부터 점점 커지는 i를 저장하고, 그 값과 XOR 비교하다 보면 남는 수가 누락한 숫자일 것이다.

코드 구현

/**
 * @param {number[]} nums
 * @return {number}
 */
const missingNumber = function(nums) {
  let storage = 0;

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

  return storage;
};

결과 분석

Runtime: 84 ms
Memory Usage: 37 MB

시간복잡도는 O(n), 공간복잡도는 O(1)이다.

🧐 또 다른 방법

솔루션 탭을 보니, 비트연산자외에 눈에 들어오는 접근법은 Gauss' Formula(가우스 계산법)이 있다. 그 유명한 초천재 가우스가 열살때 1부터 100까지의 합을 곧바로 계산했다는 그 계산법이다. 방법은 다음과 같다.

1+2+3+...+98+99+100
= (1+100)+(2+99)+...+(50+51)
= 101*50
= 5050

그리고 그것이 등차수열의 합의 기본원리이다.
등차수열의 합 공식은 (첫항 + 끝항) x 항의 수/2이다.

또 다른 코드

  1. 누락된 수 가 없을 때 총합을 구한다.
  2. 주어진 배열의 요소의 총합을 구한다.
  3. 두 값의 차이를 리턴한다.
const missingNumber = function(nums) {
  const n = nums.length;
  const total = (n * (n + 1)) / 2;
  const sum = nums.reduce((acc, cur) => acc + cur);

  return total - sum;
};

또 다른 결과

Runtime: 76 ms
Memory Usage: 36.3 MB

이것도 마찬가지로 시간복잡도 O(n), 공간복잡도 O(1)이어서 큰 차이는 없고 오히려 늦게 나올 때도 있었다. 이 방법을 시도한 이유는, 꼭 자바스크립트 메소드를 먼저 생각하지 않고도 수학문제 풀 듯 계산식을 쓰는게 오히려 간단하게 해결할 수도 있기 때문이다.

마무리

Single Number 문제로 XOR 사용법을 익히고나니 비트연산자 활용이 눈에 슬슬 보이는것 같아서 좋다.

Reference & Learn More

Single Number

Tags
Comments