LeetCode

LeetCode 287 Find the Duplicate Number 풀이: 플로이드 순환 탐지

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

중복 값을 찾는 문제처럼 보이지만, 배열을 수정할 수 없고 O(1) 추가 공간만 사용할 수 있다. 배열의 값을 다음 인덱스로 보는게 필요하고 플로이드 순환 탐지 알고리즘을 함께 적용해야하므로 까다롭다. Level 3으로 판단했다.

1. 단 하나 존재하는 중복 숫자를 반환하는 문제

길이가 n + 1인 배열 nums가 주어진다. 배열의 모든 값은 1 이상 n 이하이고, 정확히 하나의 숫자만 두 번 이상 나타난다. 이 중복 숫자를 반환해야 한다.

중요한 조건은 다음과 같다.

  • 배열의 길이는 n + 1
  • 모든 값은 [1, n] 범위에 있다
  • 중복되는 숫자는 정확히 하나
  • 배열 nums를 수정할 수 없다.
  • 추가 공간은 O(1)만 사용할 수 있다.

값의 범위에 숫자가 n + 1개 있으므로 비둘기집 원리에 따라 중복 숫자는 반드시 존재한다.

2. 플로이드 순환 알고리즘 적용하여 중복 탐지

그래프 구조와 방문 기록

배열을 다음과 같은 함수 그래프로 해석한다.

다음 위치 = nums[현재 위치]

nums[i]는 항상 1 이상 n 이하이므로, 현재 위치에서 nums[i]를 읽으면 항상 배열 안의 다음 위치로 이동할 수 있다. 따라서 0에서 시작해 값을 따라가면 다음과 같은 연결 리스트 형태가 된다.

0 -> nums[0] -> nums[nums[0]] -> ...

서로 다른 두 인덱스가 같은 값으로 이동하게 만드는 중복 숫자가 있으므로, 이 경로에는 순환이 생긴다. 이 순환이 시작되는 진입점의 값이 바로 중복 숫자다.

플로이드의 순환 탐지 알고리즘을 두 단계로 적용한다.

  1. slow는 한 번에 한 칸, fast는 한 번에 두 칸 이동시켜 순환 내부에서 만나는 지점을 찾는다.
  2. 한 포인터를 다시 시작 위치 0으로 옮긴다.
  3. 두 포인터를 모두 한 칸씩 이동하면, 두 포인터가 다시 만나는 위치가 순환의 진입점이다.

첫 번째 만남은 순환 내부의 임의 지점일 뿐 중복 숫자라고 바로 반환할 수 없다. 두 번째 단계에서 시작점과 만남 지점까지의 거리를 맞추면 순환 진입점에 도달한다.

배열 값이 순환 진입점을 가리키는 구조

이 문제의 배열은 단순히 중복 값을 저장한 목록이 아니라, 값이 다음 인덱스를 가리키는 함수 그래프로 볼 수 있다. 값의 범위가 [1, n]으로 제한되어 있기 때문에 nums[i] 를 인덱스로 사용해도 범위를 벗어나지 않는다.

중복 숫자가 여러 번 나타나는 경우에도 여러 위치가 같은 다음 위치를 가리키므로 순환은 유지된다. 예를 들어 [3, 3, 3, 3, 3]에서는 0 -> 3 -> 3이 되어 3이 순환 진입점이다.

시간·공간 복잡도

두 단계 모두 배열을 선형 횟수만큼 이동하므로 시간 복잡도는 O(n)이다. 포인터 몇 개만 사용하고 방문 집합이나 복사 배열을 만들지 않으므로 추가 공간 복잡도는 O(1)이다.

3. 문제 해결 코드 (Python)

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

        # 순환 내부에서 두 포인터가 만나는 지점을 찾는다.
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]

            if slow == fast:
                break

        # 시작점과 첫 만남 지점에서 같은 속도로 이동하면 진입점에서 만난다.
        entry = 0
        while entry != slow:
            entry = nums[entry]
            slow = nums[slow]

        return entry

fast를 두 칸 이동할 때 nums[fast]도 항상 1..n 범위이므로 별도의 경계 검사가 필요하지 않다. 첫 번째 반복문은 순환의 존재를 이용해 반드시 만남을 만들고, 두 번째 반복문은 순환 진입점까지 두 포인터를 같은 속도로 이동한다.

4. 오답 접근과 반례

집합으로 방문 값 기록하기

다음처럼 집합에 이미 본 값을 저장하면 중복을 쉽게 찾을 수 있다.

seen = set()
for num in nums:
    if num in seen:
        return num
    seen.add(num)

하지만 최대 n개의 값을 집합에 저장하므로 추가 공간이 O(n)이다. 결과는 맞더라도 문제의 O(1) 공간 조건을 만족하지 못한다.

정렬 후 인접한 값 비교하기

배열을 정렬하면 같은 값이 이웃하게 되므로 인접 원소를 비교할 수 있다. 그러나 nums.sort()는 입력 배열을 변경하며, 정렬 시간도 O(n log n)이다. 그래서 배열 수정 금지 조건과 선형 시간 요구를 동시에 만족하지 못한다.

첫 번째 포인터 만남을 바로 반환하기

두 포인터가 처음 만난 위치는 순환 내부의 임의 지점이다. 따라서 첫 만남을 곧바로 중복 값으로 반환하면 안 된다. 예를 들어 nums = [1, 3, 4, 2, 2]에서는 경로가 0 -> 1 -> 3 -> 2 -> 4 -> 2가 되고, 첫 만남 위치와 순환 진입점 2가 항상 같은 위치라는 보장은 없다. 실제 진입점을 찾으려면 두 번째 이동 단계가 필요하다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 순환 진입점과 최소 입력을 확인할 수 있다.

solver = Solution()
assert solver.findDuplicate([1, 3, 4, 2, 2]) == 2
assert solver.findDuplicate([3, 1, 3, 4, 2]) == 3
assert solver.findDuplicate([1, 1]) == 1

5. 공식 예제와 추가 검증

작성한 findDuplicate 함수를 Python으로 실행해 LeetCode 공식 예제와 경계 사례를 확인했다.

공식 예제

입력 기대 출력 확인 결과
nums = [1,3,4,2,2] 2 통과
nums = [3,1,3,4,2] 3 통과
nums = [3,3,3,3,3] 3 통과

추가 검증 1: 가장 작은 입력

입력: nums = [1, 1]
기대 출력: 1
확인 결과: 통과
검증 목적: n이 1인 최소 크기에서 순환 진입점을 찾는지 확인

추가 검증 2: 중복 값이 배열 뒤쪽에 있는 경우

입력: nums = [1, 2, 3, 4, 5, 6, 6]
기대 출력: 6
확인 결과: 통과
검증 목적: 가장 큰 값이 중복될 때 인덱스 이동이 정상인지 확인

추가 검증 3: 중복 값이 세 번 이상 나타나는 경우

입력: nums = [2, 5, 1, 1, 3, 4]
기대 출력: 1
확인 결과: 통과
검증 목적: 중복 값이 두 번이 아니라 여러 번 나타나는 조건 확인

6. 다른 풀이 방식 검색 및 비교

집합을 사용하면 O(n) 시간에 직관적으로 해결할 수 있지만 O(n) 공간이 필요하다. 값의 범위에 대한 이분 탐색은 배열을 수정하지 않고 O(1) 공간을 사용할 수 있지만, 각 단계마다 배열을 다시 세어 O(n log n) 시간이 걸린다. 이 글의 플로이드 방식은 배열을 변경하지 않으면서 O(n) 시간과 O(1) 공간을 모두 만족한다.

마무리

Find the Duplicate Number는 배열의 값을 다음 인덱스로 해석하면 연결 리스트 순환 문제로 바뀐다. 중복 값 때문에 생긴 순환의 진입점을 플로이드의 느린 포인터와 빠른 포인터로 찾으면 입력 배열을 수정하거나 별도 방문 기록을 만들지 않고도 O(n) 시간에 답을 구할 수 있다.

#투 포인터#LeetCode#난이도 3