[LinkedLists: Fast and Slow Pointers] 287. Find the Duplicate Number ★★★★★

287. Find the Duplicate Number

 

이 문제 LeetCode 287. Find the Duplicate Number는 배열을 수정하지 않고,
**O(1)**의 추가 공간만으로 중복된 숫자 하나를 찾아야 하는 문제예요.

 

내 코드

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # nums 수정하지 말고, 공간복잡도는 O(1) 로..!!
        # n+1 개수
        n = len(nums)-1
        res = 1
        for i in range(2, n+1):
            res ^= i
        
        for n in nums:
            res ^= n
        return res

 

지금 작성하신 코드는 XOR 방식을 사용한 것인데, 이 문제에서는 제약 조건 때문에 이 방법이 맞지 않습니다.

---

❌ 문제점

        for i in range(2, n+1):
            res ^= i

• 1~n까지의 XOR을 구하고
• nums 전체와 XOR해서 겹치는 수를 찾아내려는 아이디어인데,
• 이 방식은 **"정확히 한 숫자가 한 번만 더 나오는 경우"**에는 동작할 수 있으나,

예를 들어 nums = [3,3,3,3,3]처럼 같은 수가 여러 번 나오는 경우에는 XOR 결과가 무작위가 되어버려 정답이 아닙니다.

---

✅ 정답 풀이 (공간 O(1), 수정 금지): Floyd’s Tortoise and Hare (사이클 탐지)

이 문제는 배열을 링크드 리스트처럼 생각하고 사이클 탐지로 풀 수 있습니다.

---

✅ 문제 조건 요약

• nums의 길이는 n + 1
• 모든 값은 1 ~ n 범위
• 단 하나의 숫자만 중복되고, 여러 번 나타날 수 있음
• 배열을 수정하지 말 것
• O(1) extra space, O(n) time (또는 O(n log n))으로 해결해야 함

---

✅ 해결 방법 1: Floyd's Cycle Detection (빠른/느린 포인터)

이 문제는 매우 독특하게도, 연결 리스트 사이클 탐지 알고리즘으로 풀 수 있어요!

💡 왜 연결리스트처럼 생각하나?

• nums[i]를 인덱스로 보면,
  i → nums[i] → nums[nums[i]] → ... 이렇게 따라갈 수 있음
• 이건 결국 사이클이 있는 구조를 만들고,
• 중복된 숫자가 사이클의 시작점이 됨!

---

✅ 예시

nums = [1, 3, 4, 2, 2]
# 인덱스 0 → 값 1 → 인덱스 1 → 값 3 → 인덱스 3 → 값 2 → 인덱스 2 → 값 4 → 인덱스 4 → 값 2 (사이클!)

 

✅ 정답 코드 (Floyd’s Tortoise and Hare)

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # Step 1: 사이클 내부에서 만나는 지점 찾기
        slow = fast = nums[0]

        while True:
            slow = nums[slow]          # 1칸 이동
            fast = nums[nums[fast]]    # 2칸 이동
            if slow == fast:
                break

        # Step 2: 사이클 입구(중복 숫자) 찾기
        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]

        return slow

 

✅ Q) 시작을 nums[0] 말고 0 으로 해도 되는지? 0으로 해도 통과됨

→ 결국 동작은 비슷하지만, 수학적으로 정의된 Floyd’s 알고리즘 흐름을 따르려면 nums[0]으로 시작해야 정확합니다.

초기값설명

slow = nums[0]	✅ 권장 (정확한 연결 탐색 시작점)
slow = 0	❌ 시작 노드를 nums[0]보다 한 단계 더 앞에서 시작 → 논리 깨짐 가능성

그래서 꼭 이렇게 써야 합니다:

slow = fast = nums[0]

 

✅ 시간/공간 복잡도

항목	복잡도
시간	O(n)
공간	O(1) ✅

---

✅ 다른 방법 (조건 무시 시)

방법	설명조건	만족 여부
정렬 후 비교	정렬 후 인접 비교	❌ 배열 수정함
set() 사용	중복 검사	❌ 공간 O(n) 사용
이진 탐색	값의 개수 기반 범위 탐색	✅ (추가 공간 O(1), 배열 불변)

 

✅ 핵심 아이디어: 값의 범위에 이진 탐색을 적용

• 값의 범위는 1부터 n까지입니다.
• 중복이 있다면, 중복된 값 이하의 개수가 그 값보다 커집니다.

---

🔍 예시

nums = [1, 3, 4, 2, 2]

n = 4 (nums의 길이는 5 = n + 1)

중복된 숫자 = 2

• mid = 2
• <= 2인 숫자 개수는? → 1, 2, 2 → 3개
• mid보다 개수가 크면 → 중복은 left ~ mid 구간에 있음

---

✅ 정답 코드: 이진 탐색 풀이

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        left = 1
        right = len(nums) - 1  # nums는 n + 1개, 값 범위는 1~n

        while left < right:
            mid = (left + right) // 2
            count = sum(num <= mid for num in nums)

            if count > mid:
                right = mid  # 중복이 mid 이하에 있음
            else:
                left = mid + 1  # 중복이 mid 초과에 있음

        return left  # 또는 right

 

✅ 시간/공간 복잡도

항목복잡도

시간 복잡도	O(n log n)
공간 복잡도	O(1) ✅

---

✅ 예시 흐름

nums = [1, 3, 4, 2, 2]
left = 1, right = 4

→ mid = 2, count = 3 → count > mid → 중복은 왼쪽
→ mid = 1, count = 1 → count == mid → 중복은 오른쪽

결국 left = 2

 

✅ 요약

방법	특징	특징
Floyd's Cycle	✅	연결 리스트 아이디어
Binary Search	✅	값의 분포로 판단

---