투 포인터와 슬라이딩 윈도우

가격순으로 정렬된 상품 목록에서 합이 예산과 같은 두 상품을 찾는다. API 게이트웨이는 "사용자마다 최근 1초 동안 요청 3번까지"만 받는다. 로그 분석 화면은 "같은 이벤트가 반복되지 않은 가장 긴 구간"을 찾는다.

세 문제 모두 쉬운 풀이는 모든 쌍이나 모든 구간을 보는 것이다. 원소 n개면 쌍은 약 n²/2개, 구간도 약 n²/2개다(원소 6개면 15쌍, 100개면 약 5,000쌍. 1장의 n(n − 1)/2이고, 그 합이 n²/2에 가까운 이유는 『개발 수학』 Unit 4). 이 장은 포인터(pointer, 배열의 한 자리를 가리키는 인덱스 변수) 두 개를 한 방향으로만 움직이며 한 번 훑기(O(n))로 끝내는 두 가지 방법을 본다. 양 끝에서 좁혀 오는 투 포인터(two pointers)와, 구간의 왼쪽·오른쪽 끝을 함께 밀고 가는 슬라이딩 윈도우(sliding window)다. 개념 정리는 투 포인터, 슬라이딩 윈도우 노트에 있다.

양 끝 포인터: 합이 작으면 왼쪽, 크면 오른쪽

가격표가 정렬되어 있다. 가장 싼 것(lo)과 가장 비싼 것(hi)부터 더해 본다. 합이 예산보다 작으면 합을 키워야 하니 lo를 오른쪽으로 한 칸, 크면 합을 줄여야 하니 hi를 왼쪽으로 한 칸 옮긴다. 둘이 만나면 남은 쌍이 없다.

1const prices = [1, 3, 4, 6, 8, 11]2const budget = 103let lo = 04let hi = prices.length - 15let answer = '없음'6while (lo < hi) {7  const total = prices[lo] + prices[hi]8  if (total === budget) {9    answer = `${prices[lo]} + ${prices[hi]}`10    break11  } else if (total < budget) {12    lo++13  } else {14    hi--15  }16}17console.log(answer)

4 + 6

버린 후보에 답이 없는 이유

투 포인터가 맞는 답을 내려면, 한 칸 옮길 때 버리는 후보에 답이 없어야 한다. 첫 단계를 보자. 1 + 11 = 12로 예산 10을 넘었다. 이때 11은 남은 가격 중 가장 싼 1과 더해도 넘친다. 그러니 11과 짝이 되는 상품은 남은 목록에 없고, 11을 버려도 된다(hi--). 반대로 1 + 8 = 9로 모자라면, 1은 남은 가격 중 가장 비싼 8과 더해도 모자란다. 1을 버려도 된다(lo++).

매 단계 이 논리가 성립하는 것은 배열이 정렬되어 있어서다. lo 쪽이 남은 것 중 가장 작고 hi 쪽이 가장 크다는 사실이 버리는 근거다. 정렬이 깨진 배열에 같은 코드를 쓰면 답이 있는데도 없음을 낼 수 있다. 투 포인터를 볼 때마다 "무엇이 이 후보를 버려도 된다고 보장하나?"를 먼저 묻자.

슬라이딩 윈도우: 오른쪽은 늘리고, 왼쪽은 당긴다

이번엔 문자열 s에서 같은 문자가 두 번 나오지 않는 가장 긴 구간을 찾는다. 구간의 왼쪽 끝 left와 오른쪽 끝 right 사이를 윈도우라고 부른다. right를 한 칸씩 늘리다가, 새 문자가 윈도우 안에 이미 있으면 left를 그 문자를 마지막으로 본 자리 바로 다음으로 당긴다. 문자마다 마지막으로 본 위치는 last(문자 → 위치)에 적어 둔다. 마지막으로 본 자리가 left보다 앞이면 이미 윈도우 밖이니 left를 건드리지 않는다.

1const s = 'tomorrow'2const last = new Map<string, number>()3let left = 04let best = 05for (let right = 0; right < s.length; right++) {6  const ch = s[right]7  if (last.has(ch) && last.get(ch)! >= left) {8    left = last.get(ch)! + 19  }10  last.set(ch, right)11  best = Math.max(best, right - left + 1)12}13console.log(`가장 긴 길이 ${best}`)

가장 긴 길이 3

속도 제한: 최근 1초 동안의 요청

윈도우는 위치가 아니라 시간으로도 잡는다. "최근 1초 동안 요청 3번까지"는 요청 시각을 순서대로 쌓아 두고, 지금 시각보다 1초 이상 지난 요청을 앞에서부터 빼는 윈도우다. 시각은 늘 커지는 순서로 들어오니 왼쪽 끝은 앞으로만 움직인다.

1const LIMIT = 32const WINDOW_MS = 10003const times: number[] = []4let head = 05 6function allow(now: number) {7  while (head < times.length && times[head] <= now - WINDOW_MS) head++8  if (times.length - head >= LIMIT) return false9  times.push(now)10  return true11}12 13console.log([0, 100, 200, 300, 1000, 1150].map(t => allow(t)).join(' '))

0, 100, 200밀리초 요청은 통과하고 300밀리초 요청은 막힌다(최근 1초에 이미 3번). 1000밀리초에는 0밀리초 요청이 윈도우 밖으로 빠져 다시 통과하고, 1150밀리초에는 100밀리초 요청도 빠져 통과한다. 출력은 true true true false true true(Python은 True True True False True True)다. TypeScript 쪽은 배열 앞에서 빼는 shift()가 남은 원소를 모두 한 칸씩 당기는 연산이라(MDN: Array.prototype.shift) 읽을 위치 head만 옮겼다. 이 예제는 배열을 비우지 않으니 실제 서비스라면 head가 일정 크기를 넘을 때 앞부분을 잘라 내야 한다. Python은 양쪽 끝 넣기·빼기가 빠른 collections.deque를 쓴다(Python 튜토리얼: 리스트를 큐로 쓰기).

이 방식은 사용자마다 최근 요청 시각을 최대 LIMIT개 들고 있어야 한다. 사용자가 많으면 메모리를 줄이려고 1초 단위 칸마다 요청 수만 세는 근사 방식을 쓰기도 한다. 그때도 "왼쪽 끝을 앞으로 밀며 지난 것을 뺀다"는 윈도우의 뼈대는 같다.

경계에서 틀리는 줄

투 포인터와 윈도우 코드는 짧아서 경계 조건 하나가 틀려도 눈에 잘 띄지 않는다. 대부분의 입력에서 맞는 답을 내다가 특정 입력에서만 틀린다.

정리하면 틀리는 경계는 셋이다. 윈도우 밖 위치로 left를 뒤로 당기기(Math.max로 막는다), 길이를 right - left로 세기(+ 1이 빠졌다), lo <= hi로 같은 상품 두 번 더하기(lo < hi가 맞다).

nums = [1, 4, 2, 3, 5, 1], target = 8 → 2 ([3, 5])
nums = [1, 2, 1], target = 5 → 없음