이번 편의 결과물: coding-test/08-two-pointer-sliding-window/에 두 포인터·슬라이딩 윈도우 기반 풀이 4개를 작성해 node --test를 통과시킵니다. · 다루는 개념: 두 포인터 이동 패턴, 가변 크기 윈도우, 부분 배열·부분 문자열 최적화
이 편에서 만드는 파일
coding-test/
└── 08-two-pointer-sliding-window/
├── 01-two-sum-sorted/
│ ├── solution.js (+)
│ └── solution.test.js (+)
├── 02-min-length-subarray-sum/
│ ├── solution.js (+)
│ └── solution.test.js (+)
├── 03-longest-unique-substring/
│ ├── solution.js (+)
│ └── solution.test.js (+)
└── 04-three-sum/
├── solution.js (+)
└── solution.test.js (+)개념 정리
두 포인터와 슬라이딩 윈도우 비교
| 패턴 | 대표 상황 | 시간 복잡도 |
|---|---|---|
| 두 포인터(양 끝에서 좁히기) | 정렬된 배열에서 합 조건에 맞는 쌍 찾기 | O(n) |
| 가변 크기 윈도우 | 조건을 만족하는 최소·최대 구간 찾기 | O(n) |
| 세 포인터(고정 하나 + 두 포인터) | 세 수 조합 문제 | O(n²) |
두 포인터는 배열의 양 끝(또는 한쪽 끝과 이동하는 다른 끝)에서 시작해 조건에 따라 안쪽으로 좁혀갑니다. 슬라이딩 윈도우는 오른쪽 끝을 늘리며 조건을 확인하고, 조건이 깨지거나 더 줄일 수 있을 때 왼쪽 끝을 줄이는 방식입니다. 두 방식 모두 각 포인터가 배열을 최대 한 번씩만 왕복하므로, 모든 구간을 일일이 검사하는 O(n²) 방식보다 빠른 O(n)을 얻습니다.
부분 배열·부분 문자열 최적화의 핵심
윈도우가 한 칸 이동할 때 구간 전체를 다시 계산하지 않고, 빠지는 값과 들어오는 값의 “차이”만 반영합니다(예: 합에서 왼쪽 값을 빼고 오른쪽 값을 더하기). 이 차분 갱신이 슬라이딩 윈도우를 O(n)으로 만드는 핵심입니다.
실습
문제 1. 정렬된 배열에서 두 수의 합
문제 설명
오름차순 정렬된 정수 배열 numbers와 목표값 target이 주어집니다. 두 수를 더해 target이 되는 인덱스 쌍(작은 인덱스, 큰 인덱스, 0부터 시작)을 반환합니다. 정확히 한 쌍만 존재한다고 가정합니다.
입출력 예
| numbers | target | 반환값 |
|---|---|---|
[2, 7, 11, 15] | 9 | [0, 1] |
[1, 3, 4, 6, 8] | 10 | [2, 3] |
접근(복잡도)
배열이 이미 정렬되어 있으므로 왼쪽 포인터를 맨 앞, 오른쪽 포인터를 맨 뒤에 두고 두 값의 합을 target과 비교합니다. 합이 target보다 크면 오른쪽 포인터를 왼쪽으로, 작으면 왼쪽 포인터를 오른쪽으로 옮깁니다. 각 포인터가 배열을 최대 한 번씩만 이동하므로 시간 복잡도는 O(n)입니다. 04편의 해시 방식은 추가 메모리 O(n)을 쓰지만, 이 방식은 정렬되어 있다는 조건을 활용해 추가 메모리 O(1)로 풉니다.
완성 코드
// coding-test/08-two-pointer-sliding-window/01-two-sum-sorted/solution.js
export function solution(numbers, target) {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) return [left, right];
if (sum < target) {
left += 1;
} else {
right -= 1;
}
}
return [-1, -1];
}테스트
// coding-test/08-two-pointer-sliding-window/01-two-sum-sorted/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('앞뒤 두 값의 합이 target인 인덱스를 찾는다', () => {
assert.deepStrictEqual(solution([2, 7, 11, 15], 9), [0, 1]);
});
test('중간에 위치한 값들로 target을 만든다', () => {
assert.deepStrictEqual(solution([1, 3, 4, 6, 8], 10), [2, 3]);
});
test('만족하는 쌍이 없으면 [-1, -1]을 반환한다', () => {
assert.deepStrictEqual(solution([1, 2, 3], 100), [-1, -1]);
});함정
배열이 정렬되어 있다는 전제가 깨지면(정렬 안 된 배열을 그대로 넣으면) 두 포인터를 좁혀가는 방향 판단 자체가 틀립니다. 반드시 정렬된 배열에만 이 방식을 적용해야 하며, 원래 인덱스가 필요한데 배열을 직접 정렬해야 하는 상황이라면 04편의 해시 방식을 대신 씁니다.
문제 2. 합이 특정 값 이상인 최소 길이 부분 배열
문제 설명
양의 정수 배열 arr과 목표합 target이 주어집니다. 합이 target 이상이 되는 연속 부분 배열 중 길이가 가장 짧은 것의 길이를 반환합니다. 그런 부분 배열이 없으면 0을 반환합니다.
입출력 예
| arr | target | 반환값 |
|---|---|---|
[2, 3, 1, 2, 4, 3] | 7 | 2 |
[1, 1, 1, 1, 1] | 11 | 0 |
접근(복잡도)
오른쪽 포인터를 한 칸씩 늘리며 구간 합을 누적합니다. 합이 target 이상이 되면 왼쪽 포인터를 가능한 만큼 오른쪽으로 옮기며 구간을 줄이고, 그때마다 최소 길이를 갱신합니다. 각 포인터가 배열을 최대 한 번씩만 왕복하므로 전체 시간 복잡도는 O(n)입니다(모든 부분 배열을 검사하면 O(n²)입니다).
완성 코드
// coding-test/08-two-pointer-sliding-window/02-min-length-subarray-sum/solution.js
export function solution(arr, target) {
let left = 0;
let sum = 0;
let minLength = Infinity;
for (let right = 0; right < arr.length; right += 1) {
sum += arr[right];
while (sum >= target) {
minLength = Math.min(minLength, right - left + 1);
sum -= arr[left];
left += 1;
}
}
return minLength === Infinity ? 0 : minLength;
}테스트
// coding-test/08-two-pointer-sliding-window/02-min-length-subarray-sum/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('합이 target 이상이 되는 최소 길이를 찾는다', () => {
assert.strictEqual(solution([2, 3, 1, 2, 4, 3], 7), 2);
});
test('전체를 더해도 target 미만이면 0을 반환한다', () => {
assert.strictEqual(solution([1, 1, 1, 1, 1], 11), 0);
});
test('배열 전체를 더해야 target을 채우면 전체 길이를 반환한다', () => {
assert.strictEqual(solution([1, 2, 3], 6), 3);
});함정
while 대신 if로 한 번만 왼쪽을 줄이면 더 줄일 수 있는 경우를 놓쳐 최소 길이보다 큰 값이 나옵니다. 배열에 음수가 섞이면 이 방식은 성립하지 않습니다. 구간을 줄여도 합이 항상 줄어든다는 보장이 없기 때문입니다.
문제 3. 중복 없는 가장 긴 부분 문자열
문제 설명
문자열 s에서 같은 문자가 반복되지 않는 가장 긴 연속 부분 문자열의 길이를 반환합니다.
입출력 예
| s | 반환값 |
|---|---|
"abcabcbb" | 3 |
"bbbbb" | 1 |
"pwwkew" | 3 |
접근(복잡도)
오른쪽 포인터를 한 칸씩 늘리며 Set에 문자를 추가합니다. 이미 Set에 있는 문자를 만나면, 그 문자가 사라질 때까지 왼쪽 포인터를 옮기며 Set에서 제거합니다. 매 시점 Set의 크기가 현재 윈도우의 길이이자 중복 없는 부분 문자열의 길이이므로 최댓값을 갱신합니다. 각 문자는 Set에 최대 한 번 들어가고 한 번 제거되므로 전체 시간 복잡도는 O(n)입니다.
완성 코드
// coding-test/08-two-pointer-sliding-window/03-longest-unique-substring/solution.js
export function solution(s) {
const seen = new Set();
let left = 0;
let maxLength = 0;
for (let right = 0; right < s.length; right += 1) {
while (seen.has(s[right])) {
seen.delete(s[left]);
left += 1;
}
seen.add(s[right]);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}테스트
// coding-test/08-two-pointer-sliding-window/03-longest-unique-substring/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('반복되는 문자가 섞인 문자열에서 최댓값을 찾는다', () => {
assert.strictEqual(solution('abcabcbb'), 3);
});
test('모든 문자가 같으면 1이다', () => {
assert.strictEqual(solution('bbbbb'), 1);
});
test('중간에 중복이 있어도 뒤쪽 구간이 더 길 수 있다', () => {
assert.strictEqual(solution('pwwkew'), 3);
});
test('빈 문자열은 0이다', () => {
assert.strictEqual(solution(''), 0);
});함정
seen.has(s[right])가 참일 때 while로 계속 왼쪽을 줄여야 합니다. if로 한 번만 지우면 중복 문자가 여러 번 나온 경우를 놓칩니다. Set 대신 배열에 includes로 포함 여부를 확인하면 확인 한 번이 O(n)이 되어 전체가 O(n²)로 느려집니다.
문제 4. 정렬 후 세 수의 합이 0인 조합
문제 설명
정수 배열 nums에서 합이 0이 되는 서로 다른 세 수의 조합을 모두 찾아 반환합니다. 같은 조합이 중복되면 안 됩니다.
입출력 예
| nums | 반환값 |
|---|---|
[-1, 0, 1, 2, -1, -4] | [[-1, -1, 2], [-1, 0, 1]] |
접근(복잡도)
배열을 오름차순 정렬한 뒤, 인덱스 i를 하나씩 고정하고 그 뒤 구간에서 두 포인터(left = i + 1, right = 끝)로 합이 -nums[i]가 되는 쌍을 찾습니다. 정렬되어 있으므로 합이 크면 right를 왼쪽으로, 작으면 left를 오른쪽으로 옮깁니다. 같은 값을 만나면 건너뛰어 중복 조합을 막습니다. 바깥 반복이 O(n), 안쪽 두 포인터가 O(n)이라 전체 시간 복잡도는 O(n²)입니다.
완성 코드
// coding-test/08-two-pointer-sliding-window/04-three-sum/solution.js
export function solution(nums) {
const sorted = [...nums].sort((a, b) => a - b);
const result = [];
for (let i = 0; i < sorted.length - 2; i += 1) {
if (i > 0 && sorted[i] === sorted[i - 1]) continue;
let left = i + 1;
let right = sorted.length - 1;
while (left < right) {
const sum = sorted[i] + sorted[left] + sorted[right];
if (sum === 0) {
result.push([sorted[i], sorted[left], sorted[right]]);
while (left < right && sorted[left] === sorted[left + 1]) left += 1;
while (left < right && sorted[right] === sorted[right - 1]) right -= 1;
left += 1;
right -= 1;
} else if (sum < 0) {
left += 1;
} else {
right -= 1;
}
}
}
return result;
}테스트
// coding-test/08-two-pointer-sliding-window/04-three-sum/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('합이 0이 되는 세 수 조합을 모두 찾는다', () => {
const result = solution([-1, 0, 1, 2, -1, -4]);
assert.deepStrictEqual(result, [[-1, -1, 2], [-1, 0, 1]]);
});
test('조합이 없으면 빈 배열을 반환한다', () => {
assert.deepStrictEqual(solution([1, 2, 3]), []);
});
test('중복된 조합은 한 번만 담긴다', () => {
assert.deepStrictEqual(solution([0, 0, 0, 0]), [[0, 0, 0]]);
});함정
정렬하지 않고 바로 두 포인터를 적용하면 안 됩니다. 정렬 후에도 i를 고정할 때 바로 앞의 값과 같으면 건너뛰지 않으면 같은 조합이 여러 번 저장됩니다. 값을 찾은 뒤에도 left와 right를 각각 한 번씩 반드시 이동시켜야 무한 루프를 피합니다.
직접 해보기
- 문제 1의
solution을 응용해, 정렬되지 않은 배열이 주어져도 원래 인덱스를 정확히 반환하도록{ value, originalIndex }형태로 감싸 정렬한 뒤 두 포인터를 적용하는 버전을 만들어봅니다. - 문제 3의
seen을Set대신Map(문자 → 마지막으로 등장한 인덱스)으로 바꿔, 왼쪽 포인터를while반복 없이 한 번에 점프시키는 방식으로 개선해봅니다.
정답 보기(2번)
export function solutionWithMap(s) {
const lastIndex = new Map();
let left = 0;
let maxLength = 0;
for (let right = 0; right < s.length; right += 1) {
const char = s[right];
if (lastIndex.has(char) && lastIndex.get(char) >= left) {
left = lastIndex.get(char) + 1;
}
lastIndex.set(char, right);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}Map 방식은 왼쪽 포인터를 한 칸씩 옮기는 대신 중복 문자의 마지막 위치 다음으로 한 번에 점프시켜, 최악의 경우에도 각 문자를 정확히 한 번씩만 처리합니다.
자주 하는 실수
| 증상 | 원인 | 고치는 법 |
|---|---|---|
| 두 포인터 결과가 정렬 안 된 배열에서 틀림 | 좁히는 방향 판단이 정렬을 전제로 함 | 06편처럼 먼저 정렬한 뒤 적용 |
| 가변 윈도우 최소·최대 길이가 실제보다 크게 나옴 | while 대신 if로 한 번만 윈도우를 조정 | 조건을 만족하는 동안 계속 반복하도록 while 사용 |
| 음수가 섞인 배열에서 슬라이딩 윈도우 결과가 틀림 | 구간을 줄이면 합도 항상 줄어든다는 가정이 깨짐 | 음수가 있으면 누적합과 해시를 함께 쓰는 다른 접근 필요 |
| Three Sum에서 같은 조합이 중복으로 담김 | 정렬 후 같은 값을 건너뛰지 않음 | 고정 인덱스와 양쪽 포인터 모두에서 중복 값 건너뛰기 |