쉬움
Remove Duplicates from Sorted Array
코드 라인과 단계 ID를 동기화하고, 변수/포인터/배열·행렬·그래프 엔티티의 상태 스냅샷을 단계마다 갱신한다.
입력
1함수 중복제거(nums):2 느림 = 03 반복 빠름 = 1 … n-1:4 만약 nums[빠름] ≠ nums[느림]:5 느림 = 느림 + 16 nums[느림] = nums[빠름] // 새 고유값 배치7 반환 느림 + 1 // 고유값 개수
변수
- 느림
- 0
- 고유수
- 1
1 / 4느림 포인터는 마지막 고유값의 자리를 가리킵니다.
정렬돼 있으니 같은 값은 붙어 있다 — 느림/빠름 투포인터로 고유값만 앞으로 모은다.
왜 헷갈리는가
'셋(Set)에 넣으면 되지 않나' 싶지만 이 문제의 핵심은 **제자리(O(1) 공간)**로 배열 앞쪽에 정리하고 개수를 돌려주는 것이다. 정렬 전제를 활용하는 것이 셋 풀이와의 차이다.
핵심 아이디어
느림은 마지막 고유값의 자리, 빠름은 스캔. 빠름이 직전 고유값과 다른 값을 만날 때만 느림을 밀어 그 자리에 복사한다.
복잡도
시간 O(n)·공간 O(1). 셋 풀이는 O(n) 추가 공간이 들고 원래 순서/제자리 조건을 만족하지 못한다.
실무에서 어디에 쓰나
'정렬된 스트림에서 연속 중복 접기'는 데이터 파이프라인의 흔한 단계다.
- 로그/이벤트: 정렬된 시계열에서 연속 중복 접기(run-length 전처리)
- DB: 정렬된 인덱스 스캔에서 DISTINCT 구현의 기본형
- 제자리 컴팩션: 추가 버퍼 없이 배열을 압축(메모리 제약 환경)
- 머지 단계: 정렬-병합 후 중복 제거(external sort)
흔한 실수
정렬 안 된 입력에 쓰기(연속하지 않은 중복을 놓침). 빠름이 아니라 느림 기준으로 비교하지 않기.
기억할 것
- 정렬 전제 → 연속 중복만 본다.
- 제자리 O(1) 공간이 핵심.
- 느림=고유값 자리, 빠름=스캔.
- DISTINCT·컴팩션의 기본형.