쉬움
Two Sum II - Input Array Is Sorted
코드 라인과 단계 ID를 동기화하고, 변수/포인터/배열·행렬·그래프 엔티티의 상태 스냅샷을 단계마다 갱신한다.
입력
1함수 두수합_정렬(numbers, target):2 왼 = 0, 오 = n - 13 동안 왼 < 오:4 합 = numbers[왼] + numbers[오]5 만약 합 = target: 반환 [왼, 오]6 아니면 만약 합 < target: 왼 += 1 // 더 키운다7 아니면: 오 -= 1 // 더 줄인다8 반환 없음
변수
- 왼
- 0
- 오
- 3
- target
- 9
1 / 5정렬된 배열의 양끝에 포인터를 둡니다.
정렬을 활용해 양끝 투포인터로 합을 맞춘다 — 합이 크면 오른쪽을 당기고 작으면 왼쪽을 민다.
왜 헷갈리는가
일반 Two Sum(해시맵)과 헷갈린다. 여기서는 입력이 정렬돼 있어 해시맵 없이 O(1) 공간으로 풀리는 것이 핵심 차이다. '왜 포인터를 그 방향으로 움직이나'가 정렬의 단조성 덕분임을 놓친다.
핵심 아이디어
정렬돼 있으므로 합이 target보다 작으면 더 큰 값이 필요 → 왼쪽을 오른쪽으로, 크면 더 작은 값이 필요 → 오른쪽을 왼쪽으로. 매 비교가 후보 공간을 한 칸씩 확실히 줄인다.
복잡도
시간 O(n)·공간 O(1). 해시맵 풀이(O(n) 공간)보다 메모리가 낫다 — 단, 정렬 전제가 필요하다.
실무에서 어디에 쓰나
'정렬된 두 값을 맞추는' 양끝 투포인터는 병합·구간 문제의 뼈대다.
- 정렬된 두 리스트 병합·교집합(merge join의 기초)
- 구간 합/차 맞추기: 정렬된 가격·수치에서 목표 조합 탐색
- 슬라이딩/투포인터 계열 문제(3-sum, 컨테이너, 근접합)의 하위 루틴
- 시계열: 정렬된 타임스탬프에서 간격이 목표인 쌍 찾기
흔한 실수
입력이 정렬돼 있지 않은데 이 방식을 쓰기. 중복·경계(왼<오) 처리.
기억할 것
- 정렬이 전제 — 그래서 O(1) 공간.
- 단조성이 포인터 방향을 정한다.
- 3-sum 등의 하위 루틴.
- 인덱스 필요·비정렬이면 해시맵.