JavaScript로 두 개의 인자를 받는 함수를 작성해 보겠습니다. 첫 번째 인자는 숫자 배열, 두 번째 인자는 단일 숫자입니다. 이 함수는 배열에서 세 개의 숫자(존재하는 경우)를 골라 그 합이 두 번째 인자로 지정된 값과 일치하도록 만들어야 합니다.
조건을 만족하는 모든 조합(triplet)을 2차원 배열 형태로 반환하고, 해당하는 조합이 없다면 빈 배열을 반환하면 됩니다.
문제 예시
입력 배열과 목표 합계가 다음과 같다고 가정해 봅시다.
const arr = [2, 5, 7, 8, 9, 11, 1, 6]; const sum = 22;
그렇다면 출력 결과는 다음과 같아야 합니다.
const output = [ [ 2, 9, 11 ], [ 5, 6, 11 ], [ 5, 8, 9 ], [ 6, 7, 9 ] ];
접근 방법: 정렬 + 투 포인터(Two Pointer)
이 문제는 투 포인터 기법을 활용하면 효율적으로 해결할 수 있습니다.
- 먼저 배열을 오름차순으로 정렬합니다.
- 첫 번째 요소를 기준으로 고정한 뒤, 나머지 구간의 양 끝(left, right)에 포인터를 배치합니다.
- 세 수의 합이 목표값보다 작으면 left 포인터를 증가시키고, 크면 right 포인터를 감소시킵니다.
- 합이 정확히 일치하면 결과 배열에 저장하고, 중복된 조합이 포함되지 않도록 같은 값은 건너뜁니다.
이 방식은 단순한 삼중 반복문(O(n³))보다 훨씬 빠른 O(n²) 시간 복잡도로 동작합니다.
구현 코드
const arr = [2, 5, 7, 8, 9, 11, 1, 6];
const sum = 22;
const threeSum = (arr = [], sum) => {
// 배열을 오름차순 정렬
arr.sort((a, b) => a - b);
const res = [];
for (let i = 0; i < arr.length - 2; i++) {
// 중복된 기준 값 건너뛰기
if (arr[i] != arr[i - 1]) {
let left = i + 1;
let right = arr.length - 1;
while (left < right) {
const curr = arr[i] + arr[left] + arr[right];
if (curr === sum) {
res.push([arr[i], arr[left], arr[right]]);
// 중복된 값 제거 → 결과 집합에 중복 조합이 없도록 보장
while (arr[left] == arr[left + 1]) left++;
while (arr[right] == arr[right - 1]) right--;
left++;
right--;
} else if (curr < sum) {
left++;
} else if (curr > sum) {
right--;
}
}
}
}
return res;
};
console.log(threeSum(arr, sum));실행 결과
위 코드를 콘솔에서 실행하면 다음과 같은 결과가 출력됩니다.
[ [ 2, 9, 11 ], [ 5, 6, 11 ], [ 5, 8, 9 ], [ 6, 7, 9 ] ]
마무리
이처럼 정렬과 투 포인터를 결합하면 배열에서 특정 합계를 만족하는 세 요소 조합을 중복 없이 효율적으로 찾을 수 있습니다. 이 알고리즘은 코딩 테스트에서 자주 등장하는 '3Sum' 문제의 대표적인 풀이 패턴이므로 꼭 익혀두는 것이 좋습니다.