[LeetCode]Find the Duplicate Number

https://leetcode.com/problems/find-the-duplicate-number/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

주어진 숫자 배열에서 두번 이상 반복되는 숫자를 찾는 문제입니다. 나머지 숫자는 정확히 딱 1번만 등장합니다.

 

처음 시도한 답안 - 실패

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = 0
        fast = 0

        while True:
            slow += 1
            fast += 2

            if slow >= len(nums):
                slow = slow % len(nums)

            if fast >= len(nums):
                fast = fast % len(nums)

            if nums[slow] == nums[fast]:
                return nums[slow]

접근 방법

1. 처음에 시도했던 방법입니다. 1칸씩 전진하는 slow 포인터와 2칸씩 전진하는 fast 포인터를 이용하려고 했습니다.
2. slow와 fast를 반복 하다보면 언젠가 동일해지는 순간이 올 것이고 그 숫자가 반복되는 숫자라고 생각했습니다.
3. slow는 1씩 증가, fast는 2씩 증가합니다.
4. 인덱스를 탐색하기 위해 % 연산을 진행합니다.
5. 만약 slow와 fast에서의 숫자가 동일하면 반복된 숫자임을 확인하고 return 합니다.

단순하게 slow, fast 만으로 해결할 수 있을줄 알았으나, 중복되지 않은 숫자에서 slow와 fast가 동일해지는 문제가 있었습니다. 이 문제를 해결하고자 nums 배열이 짝수면 3칸씩 홀수면 2칸씩 전진하는 fast를 적용까지 해보았으나 여전히 계속해서 예외 케이스가 발생했습니다.

플로이드 알고리즘에 기반한 다른 솔루션을 찾아보게 되었습니다.

 

두번째로 시도한 답안

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # 플로이드 사이클 알고리즘

        slow = nums[0]
        fast = nums[0]

        while True:
            # 배열에 담긴 숫자를 포인터로 가정하면 링크드 리스트처럼 연결이 가능함
            # 배열안에 담긴 숫자가 배열의 길이 -1 까지라서 가능함
            slow = nums[slow] # slow는 1칸 이동
            fast = nums[nums[fast]] # fast는 2칸 이동

            if slow == fast: # 두 포인터가 만나면 (사이클이 발견되면)
                break

        slow = nums[0] # slow를 처음 위치로 옮김
        while slow != fast: # slow와 fast가 같아지는 지점까지 1칸씩 이동
            slow = nums[slow]
            fast = nums[fast]

        return slow # slow와 fast가 같아지는 곳이 중복된 숫자임 (사이클의 시작점이 됨)

    # 1 -> 3 -> 4 -> 2 -> 2
    #                ------ 
    # 3 -> 1 -> 3 -> 4 -> 2
    # -----------

접근 방법

1. slow와 fast를 이용하는 플로이드 사이클 알고리즘을 활용합니다.
2. 배열에 담긴 숫자는 모두 배열에서의 포인터로 이용할 수 있습니다. (배열에 있는 숫자들은 배열의 길이-1 만큼의 값만 가지기 때문에)
   1. slow값 자체를 포인터로 이용해 1칸을 이동합니다. 
   2. fast값 자체를 포인터로 이용해 2칸을 이동합니다.
   3. 즉, 배열을 연결리스트처럼 생각하고 1칸과 2칸을 움직이는 것입니다.
   4. 만약, 두 값이 같아지게 되면 사이클을 발견한 것입니다. 해당 지점에서 while문을 탈출합니다.
3. slow를 처음 위치로 옮깁니다.
4. slow와 fast가 같아질때까지 1칸씩 이동합니다.
5. slow와 fast가 같아지는 곳이 사이클이 시작점이자 중복된 숫자입니다.

연결리스트 문제에서 사이클이 있는지를 발견하는 문제를 풀어본적이 있어 유사하다고 생각해 slow, fast까지의 아이디어는 생각할 수 있었습니다. 배열이라는 점에서 차이가 있었으나 배열에 포함된 값을 포인터로 사용할 수 있다는 점에서 연결리스트와 동일한 개념임을 새롭게 알 수 있었습니다.

 

플로이드 사이클 알고리즘을 활용해, 사이클을 찾는것 뿐만아니라 사이클이 시작되는 지점을 찾아 중복된 숫자를 구할 수 있었습니다.

 

 

이전에 풀이했던 링크드 리스트 사이클 찾기 문제 입니다. 이 때에는 slow, fast를 활용하지는 않았습니다.

https://leffept.tistory.com/484

[LeetCode]Linked List Cycle

 

이해에 많은 도움이 된 블로그입니다.

https://fierycoding.tistory.com/45

플로이드의 토끼와 거북이 알고리즘(Floyd's Tortoise & Hare Algorithm) / 증명 / leetcode 287번 / 파이썬