쉬움
Contains Duplicate
코드 라인과 단계 ID를 동기화하고, 변수/포인터/배열·행렬·그래프 엔티티의 상태 스냅샷을 단계마다 갱신한다.
입력
1함수 containsDuplicate(nums):2 본값 = ∅ // 지금까지 본 값의 집합3 반복 i = 0 … n-1:4 만약 nums[i] ∈ 본값:5 반환 참 // 중복을 찾음6 본값.추가(nums[i]) // 지금 값을 기록7 반환 거짓 // 중복 없음
변수
- n
- 5
1 / 9지금까지 본 값을 담아 둘 빈 집합을 준비합니다.
해시셋에 넣어 가며 이미 있는 값을 만나면 중복이다.
왜 헷갈리는가
'정렬 후 인접 비교'로도 풀 수 있어 어느 쪽이 나은지 헷갈린다. 메모리를 더 쓰더라도 한 번만 훑는 해시셋이 대개 빠르다.
핵심 아이디어
'전에 본 적 있는가'만 물으면 되므로 값→존재 여부만 남기는 해시셋이면 충분하다. 처음 중복을 만나는 순간 바로 끝낸다.
복잡도
시간 O(n)·공간 O(n)(해시셋). 정렬 풀이는 시간 O(n log n)·공간 O(1). 데이터가 이미 정렬돼 있거나 메모리가 빠듯하면 정렬 쪽.
실무에서 어디에 쓰나
'유일함'을 지키는 곳이면 어디에나 있다.
- 멱등성: 같은 결제/주문 요청이 두 번 오지 않았는지 키로 검사
- 집계: 순 방문자(UV)·고유 디바이스 수 세기
- 스트림 dedup: 재전송된 메시지 거르기(정확 셋 → 대용량이면 블룸필터로 확장)
- 무결성: 업로드 파일 해시 중복 검출
흔한 실수
정규화 전에 비교(대소문자·공백·유니코드). '중복 있나?'와 '몇 번 나오나?'를 구분(후자는 카운트 맵).
기억할 것
- 존재 여부만 필요하면 셋, 개수가 필요하면 카운트 맵.
- 첫 중복에서 즉시 종료.
- 대용량 근사 허용이면 블룸필터.
- 비교 전 정규화.