[python] 토끼와 거북이 알고리즘 (LeetCode287)

LeetCode287

• n+1개의 숫자로 구성된 배열에서
• 단 하나의 숫자만 2번 이상 등장할때 그 숫자를 찾는 문제이다
• 추가 조건으로 배열내 숫자는 1 - n사이 숫자내에서 등장한다
• 예를들어 6개의 숫자로 구성된 배열이라면 배열 내 숫자는 1~5 사이의 숫자만 나오며 하나의 수만 2번이상 등장한다
• 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 풀어야 한다 (추가 배열, 자료구조 등 사용 불가)

토끼와 거북이 알고리즘 (Floyd's Tortoise & Hare Algorithm)

• 플로이드의 토끼와 거북이 알고리즘은 연결 리스트나 배열에서 사이클(순환)을 탐지하는 알고리즘 이

• 알고리즘의 기본 원리

  • 포인터 움직임
    • 거북이(slow) 포인터: 한 번에 1칸씩 이동
    • 토끼(fast) 포인터: 한 번에 2칸씩 이동
  • 사이클 탐지 방법
    • 두 포인터가 같은 지점에 만나면 사이클이 존재한다는 의미
    • 포인터가 리스트 끝에 도달하면 사이클이 없음을 의미
      

• 알고리즘의 작동 원리

  • 사이클 존재 확인
    • 토끼와 거북이가 리스트의 루트에서 출발
    • 토끼는 빠르게 두 칸씩, 거북이는 한 칸씩 이동
    • 만약 리스트에 사이클이 있다면, 두 포인터는 반드시 만나게 됨
  • 사이클 시작점 찾기
    • 첫 만남 지점에서 거북이를 시작점으로 되돌림
    • 이후 두 포인터 모두 한 칸씩 이동
    • 다시 만나는 지점이 사이클의 시작점

• 알고리즘의 장점

  • O(1)의 공간 복잡도
  • O(n)의 시간 복잡도
  • 추가 메모리 없이 사이클 탐지 가능

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

        while True:
            tuttle = nums[tuttle]
            rabbit = nums[nums[rabbit]]

            if tuttle == rabbit:
                break
        
        tuttle = nums[0]

        while tuttle != rabbit:
            tuttle = nums[tuttle]
            rabbit = nums[rabbit]
        return tuttle