문제 개요
숫자로 이루어진 배열과 목표 합(target sum)을 인수로 받아, 배열 안에서 세 수의 합이 목표 합과 정확히 일치하는 조합이 존재하는지 확인하는 함수 threeSum()을 작성해야 합니다. 조건을 만족하는 세 요소가 존재하면 해당 요소들의 인덱스를 배열 형태로 반환하고, 존재하지 않으면 -1을 반환합니다.
접근 방법
핵심 아이디어는 간단합니다. 널리 알려진 Two Sum 문제 해결 기법을 재활용하는 것입니다.
- 먼저
twoSum()함수를 작성합니다. 이 함수는 배열과 목표 합을 받아, 합이 목표 값과 일치하는 두 요소의 인덱스를 반환합니다. 해시 맵(객체)을 활용하면 선형 시간 O(N), 선형 공간으로 처리할 수 있으며, 조건을 만족하는 쌍이 없으면-1을 반환합니다. - 그다음 실제 함수인
threeSum()을 작성합니다. 이 함수는 배열의 각 요소를 하나씩 순회하면서, "현재 요소를 제외한 나머지 두 요소의 합이 (목표 합 − 현재 요소)가 되는지"를twoSum()으로 확인합니다. 조건을 만족하는 인덱스 쌍을 찾으면 현재 인덱스와 함께 반환합니다.
이 방식을 사용하면 바깥쪽 루프 N번 × 안쪽 탐색 O(N)으로, 전체 O(N²) 시간 복잡도 안에 세 요소 조합을 찾을 수 있습니다.
예제 코드
const arr = [1,2,3,4,5,6,7,8];
const twoSum = (arr, sum) => {
const map = {};
for(let i = 0; i < arr.length; i++){
if(map[sum-arr[i]]){
return [map[sum-arr[i]], i];
};
map[arr[i]] = i;
};
return -1;
};
const threeSum = (arr, sum) => {
for(let i = 0; i < arr.length; i++){
const indices = twoSum(arr, sum-arr[i]);
if(indices !== -1 && !indices.includes(i)){
return [i, ...indices];
};
};
return -1;
};
console.log(threeSum(arr, 9));
console.log(threeSum(arr, 8));
console.log(threeSum(arr, 13));
console.log(threeSum(arr, 23));
실행 결과
콘솔 출력 결과는 다음과 같습니다.
[ 0, 2, 4 ]
[ 0, 2, 3 ]
[ 0, 4, 6 ]
-1
동작 원리 살펴보기
threeSum(arr, 9)의 실행 과정을 예로 들어 보겠습니다. 인덱스 0의 값 1을 고정한 상태에서, 나머지 요소 중 합이 8(= 9 − 1)이 되는 두 요소를 twoSum()으로 찾습니다. 그 결과 인덱스 2(값 3)와 인덱스 4(값 5)가 선택되어 최종적으로 [0, 2, 4], 즉 1 + 3 + 5 = 9를 만족하는 조합이 반환됩니다. 마찬가지로 목표 합이 8일 때는 1 + 3 + 4, 13일 때는 1 + 5 + 7 조합이 각각 발견됩니다.
반면 목표 합이 23인 경우, 배열에서 가능한 최대 세 수의 합은 6 + 7 + 8 = 21이므로 조건을 만족하는 조합이 존재하지 않고, 따라서 -1이 출력됩니다.