Find the Duplicate Number

/LeetCode

문제 해석

요약

배열이 주어지는데 각 요소는 1부터 n사이의 정수이고 중복된 것이 단 하나 있다.
중복된 그 숫자를 찾아라.

전문

🇰🇷 번역

각 요소가 1과 n(포함) 사이의 정수이고, n +1개의 정수를 포함하는 nums 배열이 주어진다면, 최소 하나의 중복된 숫자가 반드시 있다고 증명하는 것이다. 오직 하나의 중복된 숫자만 있다고 가정하고, 그 중복된 번호를 찾아라.

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

주의:

  1. 배열을 수정해선 안된다(배열은 오직 읽기만 된다고 가정).
  2. 추가 공간은 오직 일정한, 상수복잡도 O(1)만 사용할 수 있다.
  3. 시간복잡도는 O(n^2)이하여야 한다..
  4. 배열엔 단 하나의 중복된 숫자가 있다. 그러나 그것은 한 번 이상 반복 될 수 있다.

🇺🇸 원문

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

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

Note:

  1. You must not modify the array (assume the array is read only).
  2. You must use only constant, O(1) extra space.
  3. Your runtime complexity should be less than O(n^2).
  4. There is only one duplicate number in the array, but it could be repeated more than once.

🤔 문제 해결 방법 구상

중복되는 것을 찾는 것은 비트연산자와, set, 수열의 합 비교 등을 하면 된다.

그러나 비트연산자는 몇 번 중복될 지 모르는 상황에선 사용하기 힘들다.
그리고 Set은 공간복잡도가 O(n)이라, 상수복잡도가 나와야하는 이 문제에선 사용해선 안될 것 같다.

그런데, 아무리 생각해도 Set 이외에는 방법을 모르겠다... 크읍.... 그래서 일단 Set과 총합을 이용하여 문제를 풀어보려 한다.

중복 되는 것을 찾는 것은 주어진 배열을 중복 안된 set에 요소가 있는지 비교하면 될 것이다.

  1. input 배열을 돌며 Set으로 저장할 것.
  2. 다만, set에 없으면 저장, 있으면 그 값이 중복이므로 그 값을 리턴

코드 구현

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

  for (const num of nums) {
    if (set.has(num)) return num;
    set.add(num);
  }
};

결과 분석

Runtime: 80 ms
Memory Usage: 38.8 MB

시간복잡도는 O(n), 공간복잡도도 O(n)이 나오게 된다. Set을 사용하지 않고 문제를 푸는 방법을 알아봐야겠다.

🧐 개선

Solution과 다른 사용자들의 방법에선 Floyd's Tortoise and Hare(Cycle Detection) 알고리즘을 사용하는 방법을 제시한다.

플로이드의 순환 찾기라고도 불리는 이 알고리즘은, 크게보면 Two Pointers의 종류 중 하나라고 할 수 있다. 토끼와 거북이 알고리즘이라고 불리는 이유이기도 한데, 빠른 포인터(토끼)와 느린 포인터(거북이)를 이용하기 때문이다. 값이 순환한다면 2개씩 이동하는 토끼와 1개씩 이동하는 거북이가 언젠간 만나는 점을 이용한 것이다.

하나의 중복되는 숫자가 있다고 가정하므로, 주어진 배열은 순환한고 할 수 있다. 그래서 플로이드 순환 찾기 알고리즘을 사용하여 개선코드를 작성해본다.

개선 코드

  1. 빠른 포인터와 느린 포인터의 값이 같아지는 순간을 찾는다.
  2. 그때 느린 포인터를 처음으로 옮기고
  3. 한 칸씩 옮겨가며, 같아지는 값을 리턴.
const findDuplicate = function(nums) {
  let slow = nums[0];
  let fast = nums[nums[0]];

  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[nums[fast]];
  }

  slow = 0;
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }

  return slow;
};

개선 결과

Runtime: 84 ms
Memory Usage: 36.1 MB

시간복잡도는 그대로 O(n), 공간복잡도는 O(1)로 개선되었다!

마무리

예전에 Linked List에서 중복되는 값을 찾는 순환되는 값을 찾는 알고리즘을 작성해봤음에도, 중복을 순환과 연결시키는 것이 쉽지않다. 리스트 형태이고, 중복관련 문제에선 토끼와 거북이를...생각해보겠습니다...

Reference & Learn More

MDN Set
Wikipedia Cycle detection

Tags
Comments