n + 1개의 정수로 이루어진 배열 nums가 있고, 모든 원소는 1부터 n 사이의 범위에 있다고 가정해 보겠습니다. 원소 개수가 값의 범위보다 하나 더 많기 때문에(비둘기집 원리), 최소 한 개의 중복 숫자가 반드시 존재합니다. 중복 숫자가 정확히 하나만 있다고 할 때, 그 중복 숫자를 찾는 것이 이번 문제의 목표입니다. 예를 들어 배열이 [1, 3, 4, 2, 2]라면 중복 숫자는 2입니다.
접근 방법: 플로이드의 토끼와 거북이 알고리즘
이 문제는 플로이드의 사이클 탐지 알고리즘(Floyd's Tortoise and Hare)으로 우아하게 해결할 수 있습니다. 핵심 아이디어는 배열을 연결 리스트처럼 해석하는 것입니다. 즉, 인덱스 i가 다음 위치 nums[i]를 가리킨다고 보면, 중복된 값이 존재하는 순간 서로 다른 두 인덱스가 같은 지점을 가리키게 되어 자연스럽게 사이클이 형성됩니다. 그리고 그 사이클의 시작점이 바로 중복 숫자입니다.
알고리즘 단계
- a와 b를 nums[0]으로 초기화합니다.
- 무한 루프 안에서 a는 한 번에 두 칸(nums[nums[a]]), b는 한 번에 한 칸(nums[b])씩 이동하고, 두 값이 만나면 루프를 종료합니다.
- ptr을 nums[0]으로 설정합니다.
- ptr과 b가 같아질 때까지 두 포인터를 한 칸씩 이동합니다.
- 두 포인터가 만난 지점(ptr)을 반환하면 그것이 곧 중복 숫자입니다.
다음 구현 예제를 통해 더 잘 이해해 보겠습니다.
구현 예제
class Solution(object):
def findDuplicate(self, nums):
hare = nums[0]
tortoise = nums[0]
while True:
hare = nums[nums[hare]]
tortoise = nums[tortoise]
if hare == tortoise:
break
ptr = nums[0]
while ptr != tortoise:
ptr = nums[ptr]
tortoise = nums[tortoise]
return ptr
ob1 = Solution()
print(ob1.findDuplicate([3, 1, 3, 4, 2]))입력
[3, 1, 3, 4, 2]
출력
3
복잡도 분석
이 알고리즘의 시간 복잡도는 O(n)이며, 추가적인 자료구조를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 배열을 수정하지 않고, 해시맵이나 정렬 없이 중복을 찾아야 하는 제약 조건에서 특히 유용한 방법입니다.