Find the Duplicate Number(Leet Code)

Leet Code에서 재밌는 알고리즘이 있어 공유해 보고자 한다. 문제의 내용은 다음과 같다.

array nums는 n+1개의 integers를 포함하고 있으며, 그 값은 1~n의 값이다.(비둘기 집 원리로 duplicate는 무조건 존재)
오직 한개의 duplicate만 있다고 가정했을 때, duplicate값을 찾아라.
Note:
1. 기존의 array를 변경해서는 안 된다.(read-only)
2. O(1)의 extra space.
3. runtime complexity < O(n^2)
4. duplicate는 하나가 있고, 한 번이상 반복될수 있다.

문제는 정말 쉽게 보이지만, Note 조건들이 조금 까다롭다.
Note 조건없이 간단하게 생각해 볼 수 있는 풀이들은,

1. 그냥 for loop 두번을 돌면서 비교한다.(runtime 초과)

2. sort를 하고 한번에 본다.(array 변경)

3. set이용(space 초과)

4. integer값들을 bit에 기억(통과)

내가 통과한 풀이인데, python의 숫자 크기의 제한이 없음을 이용하여 각각의 숫자마다 모두 bit를 이용하여 하나의 숫자에 정보를 저장하는 방식으로 문제를 풀었다. (너무 억지스럽긴 하다..) 코드는 다음과 같다.

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        ret = 0
        for n in nums:
            tmp = 1 << n
            if ret & tmp == 0:
                ret += tmp
            else:
                return n

5. Floyd's Tortoise and Hare (Cycle Detection) - 답지 풀이

이 포스팅을 작성하는 이유이다.

Linked list에서 cycle을 detection하는 알고리즘이다.
(Cycle을 시작하는 점을 return해줌)

이름에서 볼 수 있듯이, 플로이드씨의 거북이와 토끼 알고리즘이다. 2칸씩 점프하는 토끼와 1칸씩 전진하는 거북이는 cycle이 있으면, 언젠가 서로 만나다라는 것이 이 알고리즘의 기본이다. 이 때, 처음 만나는 곳을 cycle의 시작점이라 정의 할 수 없으며, 이를 찾는 while문을 한번 더 반복해줘 야한다. Leetcode에서 제시하는 풀이는 다음과 같다.
보다 수학적인 증명은 아래 유튜브 링크에 잘 설명이 되어있다.
Why Floyd's cycle detection algorithm works?

class Solution:
    def findDuplicate(self, nums):
        # Find the intersection point of the two runners.
        tortoise = hare = nums[0]
        while True:
            tortoise = nums[tortoise]
            hare = nums[nums[hare]]
            if tortoise == hare:
                break
        
        # Find the "entrance" to the cycle.
        tortoise = nums[0]
        while tortoise != hare:
            tortoise = nums[tortoise]
            hare = nums[hare]
        
        return hare

Time complexity : O(n)
Space complexity : O(1)

이 알고리즘을 이해하는 것도, 중요한 역량인 것 같지만, 1~n까지 integer값 들에서, 이를 pointer의 개념으로 이해를 확장하여 linked list의 cycle까지 전개를 하는 것도 쉽지 않을 것으로 보인다.

그래도 하나의 재밌는 알고리즘을 배운 것으로 만족한다.