코딩 테스트나 알고리즘 문제에서 자주 등장하는 대표적인 문제 중 하나가 정렬된 배열에서 두 숫자의 합 찾기입니다. 오름차순으로 정렬된 정수 배열과 목표 합계(target) 값이 주어졌을 때, 배열 안에서 서로 더했을 때 목표값이 되는 두 숫자를 찾아야 합니다.
단, 이 문제의 핵심 조건은 다음과 같습니다.
- 시간 복잡도는 O(n) — 선형 시간(Linear Time) 내에 해결해야 합니다.
- 공간 복잡도는 O(1) — 추가 메모리 없이 상수 공간(Constant Space)만 사용해야 합니다.
배열이 이미 정렬되어 있다는 점이 바로 힌트입니다. 이럴 때 가장 효율적인 방법은 투 포인터(Two Pointer) 기법입니다.
투 포인터 기법의 원리
배열의 맨 왼쪽(left)과 맨 오른쪽(right)에 각각 포인터를 둔 뒤, 두 요소의 합을 목표값과 비교하며 포인터를 이동시킵니다.
- 두 수의 합이 목표값보다 크면 → 합을 줄여야 하므로
right포인터를 왼쪽으로 이동 - 두 수의 합이 목표값보다 작으면 → 합을 키워야 하므로
left포인터를 오른쪽으로 이동 - 두 수의 합이 목표값과 같으면 → 해당 두 숫자를 반환하고 종료
포인터가 서로 교차할 때까지 탐색하기 때문에 모든 경우를 한 번씩만 확인하게 되어 선형 시간 안에 해결됩니다.
예제 코드
const arr = [4, 6, 8, 9, 11, 12, 18, 21];
const num = 27;
const findElements = (arr = [], target) => {
let left = 0;
let right = arr.length - 1;
let res = [];
while (left < right) {
let leftElement = arr[left];
let rightElement = arr[right];
if (leftElement + rightElement === target) {
res.push(arr[left]);
res.push(arr[right]);
break;
} else if (leftElement + rightElement > target) {
right--;
} else {
left++;
}
}
return res;
};
console.log(findElements(arr, num));실행 결과
[6, 21]
동작 과정 살펴보기
위 예제에서 목표값은 27입니다. 코드가 어떻게 동작하는지 단계별로 확인해 보겠습니다.
- 첫 시도: 4 + 21 = 25 → 목표값보다 작음 →
left++ - 두 번째: 6 + 21 = 27 → 목표값과 일치! → [6, 21] 반환 후 종료
이처럼 불필요한 조합을 건너뛰면서 빠르게 답에 도달할 수 있습니다. 만약 조건을 만족하는 쌍이 없다면 빈 배열 []이 반환됩니다.
마무리
정렬된 배열에서 특정 합을 찾는 문제는 해시맵(Hash Map)을 사용한 O(n) 공간 풀이도 가능하지만, 배열이 정렬되어 있다면 투 포인터 기법이 상수 공간만 사용하므로 더 효율적입니다. 이 패턴은 '두 수의 합'뿐 아니라 세 수의 합(3Sum), 회문 검사 등 다양한 알고리즘 문제에 확장하여 활용할 수 있으니 꼭 익혀두시기 바랍니다.