투 포인터를 쓸 수 있는 문제 유형 10가지

공통점은 전부 두 개의 증가하는 포인터로 어떤 조건을 만족하는 두 수(또는 구간)를 찾는 형태라는 점!

---

🔥 1. 차이(difference)가 특정 값이 되는 두 수 찾기

대표 문제: “수열에서 |A[j] – A[i]| = K 되는 쌍 찾기”

• 정렬된 배열에서
  • diff < K → right 증가
  • diff > K → left 증가
  • diff == K → 정답 처리 후 right 증가
• 딱 이 문제 다이어트 문제 구현과 동일 패턴

---

🔥 2. 두 수의 합이 특정 값이 되는 pair 찾기 (Two-Sum sorted)

예시: BOJ 3273 두 수의 합

• sum < target → left++
• sum > target → right--
• sum == target → answer++

이 문제는 하나는 증가, 하나는 감소지만
“조건 비교를 통한 포인터 이동”이라는 패턴은 동일.

---

🔥 3. 두 수의 합이 특정 값 이하인 최대 pair 수

예시: 투포인터로 배 만들기, 우산 두 개 고르는 문제 등

• weight[left] + weight[right] ≤ limit → left++
• 아니면 → right--

특정 한계를 넘지 않는 최적의 조합을 찾는 문제.

---

🔥 4. 두 수의 차이가 최소가 되는 pair 찾기

수열이 정렬되어 있을 때 가능한 가장 작은 차이를 찾는 문제
예: “수열에서 두 수의 최소 차이 찾기”

• diff < best → 업데이트
• diff == 0 → 바로 종료
• diff > best → left/right 조절

---

🔥 5. 정렬된 배열에서 제곱 수 차이 문제

즉,
x² - y² = C
를 만족하는 x, y 찾기
→ 바로 다이어트 문제와 동일 패턴
(x² - y² = (x+y)(x-y))

다른 N에서 나오는 변형 문제로 자주 등장한다.

---

🔥 6. 부분합이 특정 값 이상 되는 최소 구간 (투포인터 + 슬라이딩 윈도우)

예: BOJ 1806 “부분합”

• sum < target → right++
• sum ≥ target → 길이 갱신 후 left++

이 문제는 "합" 기반이지만
포인터를 한 번씩 증가시키는 단조 탐색이라는 점이 동일.

---

🔥 7. 연속 부분수열이 특정 조건을 만족하는 최대/최소 길이

예: “서로 다른 숫자가 K개 이하가 되도록 하는 최대 구간 길이”
투포인터로

• 조건 만족 → right++
• 조건 만족 안 함 → left++

단조성 + 윈도우라는 점에서 구조가 완전히 동일.

---

🔥 8. 두 배열에서 x + y = target 찾기

• 배열 A의 포인터 i 증가
• 배열 B의 포인터 j 감소
  두 포인터의 상방향/하방향 이동으로 target을 찾는 투포인터 패턴.

---

🔥 9. A[i] * B[j] 특정 비교 문제

예: “곱이 특정 값을 넘지 않는 쌍의 개수 세기” 같은 문제

• product < target → left++
• else → right--

sum, diff 뿐 아니라 곱에 대해서도 가능.

---

🔥 10. 두 개의 리스트 병합(Merge Two Sorted Lists)

• 두 리스트의 pointer를 각각 비교하며 오른쪽으로 이동
• 정렬된 결과를 만든다
  두 포인터가 단조하게 증가하며 전체를 스캔한다는 점에서
  투포인터의 기본형 문제.

---

📌 전체 패턴 요약

투포인터가 사용되는 상황은 다음 조건을 만족한다:

✔ 1. 배열 또는 수열이 "단조성(정렬)"을 가지고 있고

✔ 2. 포인터가 움직일 때 항상 앞으로만 가고

✔ 3. 전체 복잡도가 O(N) 또는 O(N log N)으로 해결돼야 할 때

→ 어떤 조건(합, 차이, 곱 등)을 만족하는 두 위치를 찾는 구조면 대부분 투포인터로 가능함.

---

즉,
“증가/감소에 따라 diff 단조 변화를 가진다"
= 투포인터 조건 만족

그래서 정렬도 필요 없고 투포인터가 바로 답.