투 포인터

정렬된 배열 [2, 4, 6, 9]에서 합이 10인 두 수를 찾는 과정을 손으로 따라가 봅니다.

여기서 1단계의 판단을 뜯어봅니다. 2 + 9 = 11로 이미 크다면, 9와 짝지을 수 있는 남은 값 중 가장 작은 것이 2인데도 넘쳤다는 뜻이므로 9는 어떤 값과 짝지어도 10을 만들 수 없습니다. 그래서 9를 통째로 버리고 r을 한 칸 당깁니다. 모든 쌍 6가지를 다 보지 않고 3번의 비교로 끝났습니다.

양끝 수렴형의 절차는 네 단계입니다.

1. 정렬되어 있는지 확인합니다 — 정렬이 곧 "한 방향으로만 움직여도 된다"는 근거입니다.

const sorted = [...nums].sort((a, b) => a - b); // 원본을 지키려면 복사부터

2. 양끝에 포인터를 둡니다.

let l = 0;
let r = sorted.length - 1;

3. 합을 목표와 비교해 한쪽만 움직입니다 — 두 포인터를 동시에 옮기면 후보를 건너뜁니다.

const sum = sorted[l] + sorted[r];
if (sum < target) l++;   // 키우려면 l 전진뿐
else r--;                // 줄이려면 r 후퇴뿐

4. 두 포인터가 만나면 종료합니다 — 쌍을 찾는 문제이므로 l < r이며, l <= r로 두면 같은 원소를 두 번 쓰게 됩니다.

while (l < r) { /* 3단계 반복 */ }

전체 코드:

// 양끝 수렴 — 정렬된 배열에서 합이 target인 쌍
function pairSum(sorted: number[], target: number): boolean {
  let l = 0, r = sorted.length - 1;
  while (l < r) {
    const sum = sorted[l] + sorted[r];
    if (sum === target) return true;
    if (sum < target) l++;   // 합이 작다 → 키우는 방법은 l 전진뿐
    else r--;                // 합이 크다 → 줄이는 방법은 r 후퇴뿐
  }
  return false;
}

인덱스 두 개를 규칙적으로 움직여 이중 루프를 한 번의 순회로 줄이는 상황입니다. 핵심 조건은 포인터가 한 방향으로만 움직여도 답을 놓치지 않는다는 근거(대개 정렬)가 있어야 한다는 것입니다. 각 포인터가 최대 N번 움직이므로 O(N)입니다.

• "두 수의 합/차가 K", "가장 가까운 두 수" + 정렬 가능한 배열 → 양끝 수렴형입니다.
• "앞뒤가 대칭인가"(회문) → 양끝 수렴형의 문자열 버전입니다.
• "0을 뒤로 몰아라", "중복을 제거해 앞으로 눌러 담아라" → 동방향 전진형입니다.
• 모든 쌍을 보는 O(N²) 풀이가 떠올랐는데 N이 10만 이상이라면 투 포인터를 의심합니다.
• 단, 대상이 "연속된 구간"이면 슬라이딩 윈도우 쪽입니다.

두 가지 모양이 있습니다.

양끝 수렴이 왜 안전한가: sum < target일 때 sorted[l]과 (r보다 왼쪽의) 어떤 값을 짝지어도 지금보다 작습니다. 즉 l을 전진시켜도 버려지는 후보는 전부 정답이 될 수 없는 조합 — 이 논증이 되면 투 포인터가 성립합니다.

// 동방향 전진 — 0을 뒤로 보내기 (쓰기 포인터 w)
function moveZeroes(nums: number[]): void {
  let w = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) nums[w++] = nums[i]; // 0이 아닌 값만 앞에 눌러 담기
  }
  while (w < nums.length) nums[w++] = 0;
}

three-sum류는 "하나를 고정하고 나머지를 양끝 수렴"으로 O(N²) — 정렬 후 중복 스킵이 함께 나옵니다.

• 정렬 안 된 배열에 양끝 수렴 적용 — 근거가 무너집니다. 인덱스를 보존해야 하면 (값, 원래 인덱스) 쌍으로 정렬

const bad = nums;                                   // 정렬 없이 양끝 수렴 → 오답
const good = nums
  .map((v, i) => [v, i] as [number, number])
  .sort((a, b) => a[0] - b[0]);                     // 원래 인덱스를 들고 정렬

• while (l <= r)로 같은 원소를 두 번 사용 — 쌍 문제는 l < r
• three-sum에서 중복 답 제거 누락 — 고정값·l·r 각각 "직전과 같으면 스킵"

if (i > 0 && sorted[i] === sorted[i - 1]) continue;      // 고정값 중복 스킵
while (l < r && sorted[l] === sorted[l + 1]) l++;        // 찾은 뒤 l 중복 스킵

• 동방향 패턴에서 읽기(i)와 쓰기(w) 포인터의 역할을 섞음

• 왜 O(N)인가: 양끝 수렴에서는 매 반복마다 l이 1 늘거나 r이 1 줄고, 둘 사이 간격은 절대 넓어지지 않습니다. 간격이 처음 N에서 0까지만 줄어들 수 있으므로 반복 횟수는 최대 N번입니다. 동방향 전진형도 i와 w가 각각 최대 N번 전진하므로 합쳐서 2N번, 즉 O(N)입니다.
• 정렬 비용이 지배적: 입력이 정렬되어 있지 않다면 전체는 O(N log N)입니다. 투 포인터로 줄인 것은 O(N²)에서 O(N log N)까지이며, 정렬이 이미 되어 있다는 조건이 문제에 있는지 먼저 확인하는 이유입니다.
• 해시와의 선택: 두 수의 합은 Map으로도 O(N)에 풀립니다. 정렬이 필요 없다면 해시가 유리하고, 이미 정렬되어 있거나 추가 메모리를 쓰면 안 되거나 three-sum처럼 중복 처리가 얽히면 투 포인터가 유리합니다.
• 슬라이딩 윈도우와의 관계: 슬라이딩 윈도우도 포인터 두 개를 쓰지만 둘 다 오른쪽으로만 움직이며 그 사이가 "현재 구간"을 의미합니다. 투 포인터가 두 원소의 짝을 다루는 반면 슬라이딩 윈도우는 연속 구간의 합·길이를 다룹니다.
• 일반화된 성립 조건: 판정식이 l이 커질수록 한 방향으로, r이 커질수록 반대 방향으로 단조롭게 변할 때만 성립합니다. 값에 음수가 섞이거나 조건이 단조롭지 않으면(예: 곱이 최대인 쌍) 같은 논증이 무너지므로 다른 접근이 필요합니다.

시각화로 "버려지는 절반엔 답이 없다"는 감각을 익힌 뒤, 양끝 수렴 기본 → in-place 압축 → three-sum 순으로. 다음 토픽인 슬라이딩 윈도우는 이 기법의 "구간" 버전입니다.