쉬움
Two Sum
코드 라인과 단계 ID를 동기화하고, 변수/포인터/배열·행렬·그래프 엔티티의 상태 스냅샷을 단계마다 갱신한다.
입력
1함수 twoSum(nums, target):2 본값 = {} // 값 → 인덱스3 반복 i = 0 … n-1:4 필요 = target - nums[i] // 짝이 될 값5 만약 필요 ∈ 본값:6 반환 [본값[필요], i] // 짝을 찾음7 본값[nums[i]] = i // 지금 값을 기록8 반환 [] // 짝이 없음
변수
- target
- 9
- n
- 4
1 / 7값을 인덱스로 되찾을 빈 해시맵을 준비합니다.
해시맵으로 '짝이 될 값을 이미 봤는가'를 O(1)에 물어, 배열을 한 번만 훑고 두 수를 찾는다.
왜 헷갈리는가
이중 반복(O(n²))으로도 풀리기 때문에 해시맵이 왜 필요한지 와닿지 않는다. 또 '정렬 후 양끝 투포인터' 풀이와 자주 헷갈리는데, 그 풀이는 정렬이 원래 인덱스를 흐트러뜨려 '인덱스를 반환하라'는 이 문제에는 오히려 불리하다.
핵심 아이디어
각 원소에서 필요한 짝은 target − 현재값 하나로 정해진다. 그 값을 앞에서 이미 봤다면 답이고, 아니라면 지금 값을 '값 → 인덱스'로 해시맵에 적어 둔다.
'묻고 나서 기록한다'는 순서가 중요하다. 먼저 기록하면 자기 자신을 짝으로 골라 버린다.
복잡도
시간 O(n), 공간 O(n). 해시맵을 위한 추가 메모리를 시간과 맞바꾼다. 정렬+투포인터는 시간 O(n log n)·공간 O(1)이라, 메모리가 극도로 빠듯하고 인덱스가 필요 없을 때만 유리하다.
실무에서 어디에 쓰나
'합/차가 특정 값이 되는 한 쌍'을 빠르게 찾는 문제는 어디에나 있다.
- 결제·정산: 서로 상쇄되는 거래 쌍(입금 −출금)을 찾아 자동 매칭
- 추천: 예산에 딱 맞는 상품 두 개 묶음 제안
- 관측: 요청 로그와 응답 로그를 상관키로 짝지어 지연 계산
- 보안: 합이 임계에 닿는 이벤트 쌍 탐지(레이트/사기)
흔한 실수
같은 원소를 두 번 사용(먼저 조회, 나중 기록으로 방지). 중복 값이 있을 때 어느 인덱스를 쓰는지 명확히 하기.
기억할 것
- '이미 본 값'을 O(1)에 되찾는 문제면 해시맵을 먼저 떠올린다.
- 묻기 → 기록 순서를 지켜 자기 자신을 짝으로 고르지 않는다.
- 인덱스를 돌려줘야 하면 정렬 풀이보다 해시맵이 낫다.
- 시간을 메모리와 맞바꾸는 전형(O(n²)→O(n)).