JavaScript에서 목표 합계가 되는 모든 숫자 쌍 찾는 방법

이번 글에서는 첫 번째 인자로 숫자 배열을, 두 번째 인자로 목표 합계(target sum)를 받아, 배열 안에서 두 수를 더했을 때 목표 합계가 되는 모든 숫자 쌍을 찾아 반환하는 JavaScript 함수를 작성해 보겠습니다.

예를 들어 배열 [7, 0, -4, 5, 2, 3]에서 목표 합계가 5라면, 함수는 [0, 5]와 [2, 3]이라는 두 개의 쌍을 반환해야 합니다.

접근 방식: 해시 맵 활용

이 문제는 해시 맵(일반 객체)을 활용하면 효율적으로 해결할 수 있습니다. 배열을 한 번만 순회하면서 각 요소에 대해 '목표 합계에서 현재 값을 뺀 보완 값(complement)'을 맵에 미리 기록해 둡니다.

이후 순회 중인 현재 값이 이미 맵에 존재한다면, 그 값은 앞서 등장한 어떤 값의 보완 값이라는 의미이므로 해당 쌍을 결과 배열에 추가하면 됩니다. 이 방식의 시간 복잡도는 O(n)으로, 이중 반복문을 사용하는 O(n²) 완전 탐색보다 훨씬 빠릅니다.

예제 코드

const arr = [7, 0, -4, 5, 2, 3];
const allTwoSum = (arr, target) => {
    const map = {};
    const results = [];
    for (let i = 0; i < arr.length; i++) {
        if (map[arr[i]]) {
            results.push([target - arr[i], arr[i]]);
            continue;
        };
        map[target - arr[i]] = true;
    };
    return results;
};
console.log(allTwoSum(arr, 5));

실행 결과

콘솔에는 다음과 같이 출력됩니다.

[ [ 0, 5 ], [ 2, 3 ] ]

코드 동작 원리

map 객체는 아직 짝을 찾지 못한 보완 값을 임시로 저장하는 역할을 하고, results 배열은 완성된 쌍들을 모아둡니다.

반복문 안에서 현재 요소 arr[i]가 이미 map에 존재하면, 이는 이전에 등장한 어떤 값과 더했을 때 목표 합계가 된다는 뜻이므로 [target - arr[i], arr[i]] 쌍을 results에 push한 뒤 continue로 다음 요소로 넘어갑니다.

아직 존재하지 않는다면 target - arr[i]를 map에 true로 저장해 두어, 이후 순회에서 매칭될 수 있도록 준비합니다. 이처럼 단 한 번의 순회로 모든 쌍을 찾을 수 있습니다.