투 포인터 (Two Pointer)

관련 문제

문제	난이도	핵심
구명보트	Lv.2	투 포인터 + 그리디
두 수의 합	Lv.3	정렬 + 투 포인터
연속 부분 수열 합의 개수	Lv.2	슬라이딩 윈도우

---

1. 개념

투 포인터는 두 개의 인덱스를 사용해서 탐색 범위를 좁혀나가는 방식이다.

브루트포스로 O(N²)이 걸리는 문제를 O(N)으로 줄일 수 있다는 게 핵심이다.

정렬된 배열에서 합이 target인 두 수를 찾는 경우

브루트포스: 모든 쌍 (i, j) 확인 → O(N²)
투 포인터: left, right를 양 끝에서 좁혀옴 → O(N)

---

2. 동작 과정

[1, 2, 3, 4, 5] 에서 합이 6인 쌍 찾기

left	right	합	동작
1	5	6	✅ 정답 → left++, right--
2	4	6	✅ 정답 → left++, right--
3	3	-	left >= right → 종료

합이 target보다 크면 right를 줄이고, 작으면 left를 늘린다.

---

3. 핵심 사용 패턴

양 끝에서 좁혀오는 패턴

정렬된 배열에서 두 수의 합을 구할 때 가장 많이 쓰인다.

left = 0, right = n - 1

while left < right:
    합이 크면 → right--
    합이 작으면 → left++
    합이 같으면 → 정답 처리

같은 방향으로 이동하는 패턴 (슬라이딩 윈도우)

연속된 구간의 합이나 개수를 구할 때 사용한다.

left = 0, right = 0

right를 늘리면서 조건을 만족하는 구간 탐색
조건을 초과하면 left를 늘려서 구간 축소

---

4. 핵심 포인트 2가지

정렬이 전제되는 경우가 많다

투 포인터는 정렬된 배열에서 양 끝을 좁혀오는 방식이기 때문에, 대부분 Arrays.sort() 후에 적용한다. 정렬 없이 투 포인터를 쓰면 틀린 결과가 나올 수 있다.

left < right 조건을 지켜라

양 끝에서 좁혀오는 패턴에서 left == right가 되면 같은 원소를 두 번 쓰는 게 되므로 반드시 left < right일 때만 반복한다.

---

5. 이분탐색과의 차이

	투 포인터	이분탐색
포인터 수	2개	3개 (left, right, mid)
목적	두 원소의 관계 탐색	특정 값 탐색
이동 방식	조건에 따라 left 또는 right 이동	절반씩 범위 축소
정렬 필요	대부분 필요	반드시 필요

---

6. 시간복잡도

유형	시간복잡도	비고
투 포인터 탐색	O(N)	각 포인터가 최대 N번 이동
정렬 + 투 포인터	O(N log N)	정렬이 병목

---

7. 주의사항

• 정렬 먼저 해라. 양 끝에서 좁혀오는 패턴은 정렬된 배열에서만 유효하다.
• left < right 조건을 빠뜨리지 마라. 같은 원소를 두 번 선택하는 실수가 잦다.
• 포인터 이동 방향을 명확히 해라. 합이 크면 right--, 작으면 left++이 기본 규칙이다.
• 슬라이딩 윈도우와 구분해라. 양 끝에서 좁혀오면 투 포인터, 같은 방향으로 이동하면 슬라이딩 윈도우다.