← 전체 회차
A-042● Day 422026.06.17mediumleetcode #287neetcode150

중복된 숫자 찾기

#array#two-pointers#binary-search#bit-manipulation
↗ leetcode #287 · find-the-duplicate-number
01

문제

· problem
P.042

중복된 숫자 찾기

↗ leetcode #287

n + 1개의 정수를 포함하는 정수 배열 nums가 주어지며, 각 정수는 [1, n] 범위 내에 있습니다. nums에는 정확히 하나의 중복된 숫자가 있습니다. 이 중복된 숫자를 반환해야 합니다. 배열 nums를 수정하지 않고 O(1) 상수 추가 공간만을 사용하여 문제를 풀어야 합니다.

제약
  • · 1 ≤ n ≤ 10^5
  • · nums.length == n + 1
  • · 1 ≤ nums[i] ≤ n
  • · Precisely one integer appears two or more times
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[1,3,4,2,2]
2
example 2input → output
[3,1,3,4,2]
3
example 3input → output
[3,3,3,3,3]
3
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    중복된 숫자가 2번만 나타날까요, 아니면 더 많이 나타날 수 있을까요?
  • ☐
    왜 배열을 수정하지 않아야 할까요?
  • ☐
    'O(1) 추가 공간'은 무엇을 의미하나요?
  • ☐
    배열에 반드시 중복이 존재한다고 보장할 수 있나요?
  • ☐
    해시 집합을 사용하면 O(n) 시간에 풀 수 있나요?
  • ☐
    배열을 정렬한 후 인접한 원소를 비교하면 안 될까요?
  • ☐
    배열 인덱스를 연결 리스트 포인터처럼 생각할 수 있을까요?
  • ☐
    느린 포인터와 빠른 포인터가 만나는 지점이 정확히 중복이 위치한 인덱스일까요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 두 포인터 초기화
○
slow, fast = 0, 0
○
slow, fast = 0, 1
○
slow, fast = 1, 1
step 2· 사이클 감지: 포인터 이동│ 중첩
○
fast = nums[nums[fast]]
○
slow = nums[slow]; fast = nums[fast]
○
slow = nums[slow]; fast = nums[nums[nums[fast]]]
step 3· 사이클 감지 조건│ │ 중첩
○
if slow == fast:
○
if slow < fast:
○
if slow != fast:
step 4· 사이클 진입점 찾기: 포인터 초기화
○
slow2 = 0
○
slow = 0; slow2 = slow
○
slow2 = fast
step 5· 사이클 진입점에서 중복 찾기│ 중첩
○
return slow
○
return slow2
○
return fast
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def findDuplicate(self, nums: List[int]) -> int:
3
        slow, fast = 0, 0
4
        while True:
5
            slow = nums[slow]
6
            fast = nums[nums[fast]]
7
            if slow == fast:
8
                break
9
10
        slow2 = 0
11
        while True:
12
            slow = nums[slow]
13
            slow2 = nums[slow2]
14
            if slow == slow2:
15
                return slow
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[1,3,4,2,2]
→
2
case 2
[3,1,3,4,2]
→
3
case 3
[3,3,3,3,3]
→
3
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.