Find the Duplicate Number
1부터 n까지의 정수로 이루어진 n+1개의 원소를 가진 배열 nums가 주어집니다. 정확히 하나의 값이 한 번 이상 중복해서 나타나며, 그 값을 반환합니다.
nums를 변경하지 않고 추가 메모리를 상수만큼만 사용하여 문제를 해결하세요.
함수
- numsinteger-array
- 각각 1부터 n 사이인 정수 n+1개
- 반환값integer
- 두 번 이상 나타나는 값
제약 조건
1 ≤ n ≤ 104nums.length == n+11 ≤ nums[i] ≤ n- 정확히 하나의 값이 두 번 이상 나타나며, 다른 모든 값은 최대 한 번만 나타납니다.
예제
- 입력
- nums = [2, 5, 1, 3, 5, 4]
- 출력
- 5
- 설명
- 여기서
n은 5이고, 5는 위치 1과 4에 있으므로 답은 5입니다. 1부터 5까지의 다른 모든 값은 한 번씩 나타납니다.
- 입력
- nums = [4, 2, 4, 1, 4]
- 출력
- 4
- 설명
- 4는 위치 0, 2, 4에 세 번 나타나고, 3은 전혀 나타나지 않습니다. 반복된 값 하나가 여러 개의 누락된 값을 대신할 수 있으므로 답은 4입니다.
제출 시 숨은 테스트 +17개
후속 질문
값에 대한 이진 탐색은 두 규칙을 모두 O(n log n) 시간에 유지합니다. 두 규칙을 O(n) 시간에 유지할 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
모든 값은 1과
n사이에 있고, 배열에는 0부터n까지의 위치가 있습니다. 따라서 모든 값은 유효한 위치이기도 합니다. 위치 0에서 시작해 위치nums[0]로 이동하고, 그다음에는 해당 값이 가리키는 위치로 이동하는 식으로 계속합니다. 이 이동 과정에서는 어떤 일이 일어나야 할까요?이 이동은 멈추지 않고 방문할 위치가
n+1개뿐이므로 루프에 빠집니다. 루프에 진입하는 위치에는 서로 다른 두 위치에서 도달하며, 두 위치 모두 그 위치를 값으로 갖습니다.위치 0에서 두 포인터로 루프의 진입점을 찾습니다. 한 포인터는 한 번에 한 칸씩, 다른 포인터는 두 칸씩 이동하여 같은 위치에 도달할 때까지 반복합니다. 그런 다음 한 포인터를 0으로 되돌리고 두 포인터를 한 번에 한 칸씩 이동합니다. 두 포인터가 만나는 지점이 진입점이며, 이것이 답입니다.
풀이
해시 집합이나 정렬을 사용하면 중복 값을 바로 찾을 수 있지만, 둘 다 규칙을 위반합니다. 집합은 모든 값을 저장할 메모리가 필요하고, 정렬은 nums를 변경합니다. 해결 방법은 숫자에 있습니다. 모든 값은 1부터 n 사이이므로 배열에서 유효한 위치이기도 합니다. 각 값을 다른 위치를 가리키는 링크로 보고, 위치 0에서 링크를 따라가면 항상 중복 값이 입구인 루프에 도달합니다. Floyd의 빠른 포인터와 느린 포인터를 사용하면 정수 두 개로 그 입구를 찾을 수 있습니다.
모든 쌍 비교하기
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
반복되는 값은 최소한 두 위치 i < j에 있습니다. 각 위치를 그 뒤에 있는 모든 위치와 비교합니다. 값이 같은 첫 번째 쌍이 답입니다. 첫 번째 예시에서 위치 1에는 5가 있고, 위치 2부터 끝까지 살펴보면 위치 4에서 또 다른 5를 찾습니다.
이 방법은 두 가지 규칙을 모두 지킵니다. 아무것도 쓰지 않으며, 기억하는 것은 두 개의 루프 카운터뿐입니다. 쌍들을 비교하기 때문에 느립니다. 값이 n+1 = 10,001개이고 두 복사본이 모두 끝부분에 가까이 있으면 약 5 × 10^7개의 쌍을 확인합니다.
알고리즘
- 0부터 끝까지 각 위치
i에 대해: i다음의 각 위치j에 대해nums[i]와nums[j]를 비교합니다.- 처음 일치하는 항목에서
nums[i]를 반환합니다.
def findDuplicate(nums):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j]:
return nums[i]
return -1 # unreachable: the input always holds a repeat값을 기준으로 이진 검색
핵심 아이디어
위치가 아니라 값의 범위를 탐색하세요. 경계값 m을 정하고 nums의 원소 중 m 이하인 것이 몇 개인지 세세요.
중복된 값 d가 m보다 크면, 1부터 m까지의 각 값은 최대 한 번만 나타나므로 개수는 최대 m입니다. d가 m 이하라면, m보다 큰 값은 각각 최대 한 번만 나타나므로 m보다 큰 원소는 최대 n-m개이고, m 이하인 원소는 적어도 m+1개입니다. 따라서 "count > m" 검사는 d보다 작은 모든 m에서는 거짓이고, d부터는 참입니다. 이분 탐색으로 참이 되는 첫 번째 m을 찾으면, 그 값이 d입니다.
두 번째 예시에서 n은 4입니다. m = 2일 때 원소 2와 1의 개수는 2이므로 2보다 많지 않아 답은 2보다 큽니다. m = 3일 때도 개수는 여전히 2이므로 답은 4입니다. 각 라운드에서 배열 전체를 한 번 읽고 범위를 절반으로 줄이므로, 작업량은 O(n log n)입니다. 10,001개의 값을 약 14번 훑는 셈입니다.
알고리즘
low를 1로 설정하고,high를n, 즉nums의 길이에서 1을 뺀 값으로 설정합니다.low < high인 동안 두 값의 중간에mid를 설정합니다.nums에서mid이하인 항목의 개수를 셉니다.- 개수가
mid보다 크면high를mid로 설정하고, 그렇지 않으면low를mid+1로 설정합니다. low를 반환합니다.
def findDuplicate(nums):
low, high = 1, len(nums) - 1
while low < high:
mid = (low + high) // 2
# How many values fall in 1..mid?
count = 0
for x in nums:
if x <= mid:
count += 1
if count > mid:
high = mid # 1..mid holds more values than it has room for
else:
low = mid + 1 # the repeat is above mid
return low값 링크에서 플로이드의 사이클 탐지
핵심 아이디어
배열을 링크로 생각하세요. 위치 i는 위치 nums[i]를 가리킵니다. 0부터 n까지의 모든 위치에는 나가는 링크가 정확히 하나씩 있고, 모든 링크는 1부터 n 사이의 위치로 이어집니다. 첫 번째 예시의 링크는 0 → 2, 1 → 5, 2 → 1, 3 → 3, 4 → 5, 5 → 4입니다.
위치 0에서 시작해 링크를 따라가세요. 모든 위치에는 링크가 있고 위치는 n+1개뿐이므로, 이동은 결코 멈추지 않고 반드시 이미 방문한 위치로 돌아옵니다. 그때부터는 계속 순환합니다. 이 경로는 꼬리 뒤에 루프가 이어지는 형태로, 그리스 문자 ρ처럼 생겼습니다. 첫 번째 예시에서 이동 경로는 0, 2, 1, 5, 4, 5, 4, …입니다. 꼬리는 0, 2, 1이고 루프는 5, 4입니다. 위치 3은 자기 자신을 가리키지만, 이동 경로가 그곳에 도달하지 않으므로 문제가 되지 않습니다.
루프의 진입점이 중복 값입니다. 이동 경로는 서로 다른 위치에서 두 번 5에 진입합니다. 한 번은 꼬리의 끝인 위치 1에서입니다(nums[1]이 5이므로). 또 한 번은 루프의 끝인 위치 4에서입니다(nums[4]가 5이므로). 서로 다른 두 위치에 값 5가 있으므로 5가 중복됩니다. 꼬리에는 항상 위치 0이 포함됩니다. 어떤 값도 0이 아니며, 어떤 링크도 0으로 되돌아가지 않기 때문입니다. 따라서 진입점에는 항상 서로 다른 두 경로가 있습니다. 값은 정확히 하나만 중복되므로 진입점이 바로 그 값입니다.
이제 연결 리스트의 사이클 탐지에서처럼 두 포인터를 사용해 진입점을 찾으세요. 1단계에서는 두 포인터가 루프 안의 같은 위치에 설 때까지 slow는 한 번에 링크 하나를, fast는 한 번에 링크 두 개를 따라갑니다. 첫 번째 예시에서는 두 포인터가 4에서 만납니다. 2단계에서는 slow를 0으로 되돌리고 fast는 그대로 둔 다음, 두 포인터를 매번 링크 하나씩 이동합니다. 그러면 진입점에서 만납니다.
2단계가 작동하는 이유는 다음과 같습니다. 꼬리에서 진입점까지 가는 데 링크 T개가 필요하고, 루프에는 위치가 C개 있다고 합시다. 두 포인터가 만났을 때 slow는 s걸음을, fast는 2s걸음을 이동했습니다. 두 포인터가 같은 위치에 있었으므로 fast가 추가로 이동한 s걸음은 루프를 정수 바퀴 돈 거리입니다. 그 뒤 T걸음 더 이동하면 slow는 0에서 출발해 진입점에 도달하고, fast는 0에서 출발한 이동 경로가 s+T걸음 뒤에 도달하는 위치에 서 있습니다. fast가 추가로 돈 바퀴는 위치를 바꾸지 않기 때문입니다. 이는 진입점까지의 T걸음에 s걸음을 더한 것으로, 루프를 정수 바퀴 돈 거리이므로 fast도 진입점에 도달합니다. 두 포인터는 그보다 일찍 만날 수 없습니다. slow는 아직 꼬리에 있고 fast는 루프를 벗어나지 않기 때문입니다. 첫 번째 예시에서는 slow가 2, 1, 5로 이동하고 fast가 5, 4, 5로 이동해 T = 3걸음 뒤에 5에서 만납니다.
각 단계는 O(n)걸음이 걸리고, 사용하는 메모리는 두 위치뿐이며, nums에는 값을 쓰지 않습니다.
알고리즘
- 각 위치
i를 위치nums[i]에 연결된 노드로 취급하고, 두 포인터를 모두 위치 0에서 시작합니다. - 1단계: 두 포인터가 같아질 때까지
slow를nums[slow]로 이동하고fast를nums[nums[fast]]로 이동합니다. - 2단계:
slow를 다시 0으로 설정합니다. - 두 포인터가 같아질 때까지 한 번에 링크 하나씩 이동합니다.
slow는nums[slow]로,fast는nums[fast]로 이동합니다. - 해당 위치를 반환합니다. 이 위치가 반복되는 값입니다.
def findDuplicate(nums):
# Treat each index i as a node with one link, to nums[i].
# Phase 1: slow moves one link, fast moves two, until they meet in the cycle.
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Phase 2: restart one pointer at index 0 and move both one link at a time.
# They meet at the cycle's entrance, the index two positions link to.
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
함정과 경계 사례
대부분의 오답은 위치와 값을 혼동하거나, Floyd의 방법을 한 단계 일찍 멈춰서 발생합니다.
- 1단계의 만나는 지점을 반환하는 경우. 이 지점은 루프 안의 어떤 위치일 뿐, 반드시 진입점인 것은 아닙니다. 첫 번째 예시에서 포인터는 4에서 만나지만, 정답은 5입니다.
- 처음 이동하기 전에
slow == fast를 확인하는 경우. 둘 다 0에서 시작하므로 루프가 즉시 끝납니다. 먼저 이동한 다음 비교하거나, 두 포인터를 각각 한 칸과 두 칸 앞에서 시작하세요. - 위치 0이 아닌 곳에서 탐색을 시작하는 경우. 값이 0인 항목이 없으므로 어떤 링크도 위치 0을 가리키지 않으며, 이것이 꼬리 부분을 보장합니다. 다른 위치에서 시작하면 외부에서 진입할 방법이 없는 루프에 들어갈 수 있습니다. 예를 들어 첫 번째 예시의 위치 3은 진입점이어도 아무것도 증명하지 못합니다.
- 중복된 값이 정확히 두 번 나타난다고 가정하는 경우. 합계 계산 방법인 전체 합계에서
1 + 2 + ... + n을 빼는 방식은 두 번째 예시에서 15 - 10 = 5를 반환하지만, 정답은 4입니다. XOR 방식도 마찬가지입니다. - 값이 아닌 위치를 대상으로 이진 탐색을 하거나
count >= mid를 검사하는 경우. 1부터m까지의 값 중 반복되거나 누락된 값이 없으면m이하인 값의 개수는 정확히m이므로, 양쪽을 구분하는 조건은>뿐입니다. nums[x]의 부호를 바꾸거나 값을 제자리로 옮겨 방문한 값을 표시하는 경우. 두 방법 모두 작동하지만 배열을 변경하며, 이는 과제에서 금지합니다.
자주 묻는 질문4
중복된 숫자 찾기의 시간 복잡도는 얼마인가요?
Floyd의 사이클 탐지는 O(n) 시간과 O(1) 추가 메모리로 실행됩니다. 두 단계 각각에서 최대 몇 배의 n개 링크를 따라갑니다. 값에 대한 이진 탐색은 O(n log n) 시간과 O(1) 메모리를 사용합니다. 모든 쌍을 비교하는 방법은 O(n²)입니다.
플로이드의 순환 탐지 알고리즘은 왜 중복된 숫자를 찾을까요?
각 값을 현재 위치에서 값이 가리키는 위치로 이어지는 링크로 읽으면, 위치 0에서 시작하는 이동은 반드시 루프에서 끝나야 합니다. 멈추지 않고 이동할 수 있는 위치는 n+1개뿐이기 때문입니다. 루프에 진입하는 위치는 꼬리 부분의 위치 하나와 루프 안의 위치 하나, 이렇게 서로 다른 두 위치에서 도달할 수 있으므로 두 항목이 그 값을 가집니다. Floyd의 방법은 두 개의 포인터로 루프의 진입점을 찾으므로, 반복되는 값을 찾습니다.
해시 집합을 사용하거나 배열을 정렬하면 안 되나요?
둘 다 O(n) 또는 O(n log n) 시간 안에 답을 찾으며, 실제 프로그램에서는 어느 방법을 사용해도 괜찮습니다. 이 문제에서 일부러 두 방법을 금지한 이유는 해시 집합을 사용하면 O(n)의 추가 메모리가 필요하고, 정렬하면 nums가 변경되거나 전체 복사본이 필요하기 때문입니다. 이러한 제약이 사이클 관점으로 접근하도록 이끕니다.
중복 숫자 찾기 문제에서는 왜 합계 공식이 작동하지 않나요?
배열의 합에서 1 + 2 + ... + n을 빼면 중복값이 정확히 두 번 나타나고 다른 모든 값은 한 번씩 나타나는 경우에만 중복값을 얻을 수 있습니다. 여기서는 반복되는 값이 여러 번 나타날 수 있고 누락된 값을 대신할 수도 있습니다. [4, 2, 4, 1, 4]에서 차이는 15 빼기 10 = 5이며, 배열에 5는 아예 없습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def findDuplicate(nums):
# 여기에 코드를 작성하세요케이스 1
케이스 2
입력
nums = [2, 5, 1, 3, 5, 4]
기대값
5