이번 글에서는 정수 배열에서 합이 특정 목표값(target)이 되는 두 숫자를 찾는 Two Sum(두 수의 합) 문제를 선형 시간, 즉 O(n) 안에 해결하는 자바스크립트 함수를 작성해 보겠습니다.
Two Sum 문제란?
정수로 이루어진 배열이 하나 주어지고, 그중 두 숫자를 골라 그 합이 특정 목표값과 정확히 일치하도록 만들어야 합니다.
twoSum 함수는 조건을 만족하는 두 숫자의 인덱스를 배열 형태로 반환해야 하며, 어떤 두 요소의 합도 목표값이 되지 않는다면 빈 배열([])을 반환해야 합니다.
해시맵으로 O(n) 시간에 풀기
모든 두 수의 조합을 일일이 검사하는 브루트 포스 방식은 O(n²)이 걸리지만, 해시맵(객체)을 활용하면 단 한 번의 순회만으로 문제를 해결할 수 있습니다.
동작 원리는 다음과 같습니다.
- 배열을 순회하면서 지금까지 등장한 숫자와 해당 인덱스를 해시맵에 기록합니다.
- 각 단계에서 현재 요소와 더했을 때 목표값이 되는 수, 즉
sum - arr[i]가 이미 해시맵에 존재하는지 확인합니다. - 존재한다면 저장된 인덱스와 현재 인덱스를 담은 배열을 즉시 반환합니다.
- 끝까지 조건을 만족하는 쌍을 찾지 못하면 빈 배열을 반환합니다.
해시맵의 탐색과 삽입은 평균적으로 O(1)이므로 전체 시간 복잡도는 O(n)이 되며, 최악의 경우 공간 복잡도는 O(n)입니다.
예제 코드
const arr = [2, 5, 7, 8, 1, 3, 6, 9, 4];
const sum = 10;
const twoSum = (arr, sum) => {
const map = {};
for (let i = 0; i < arr.length; i++) {
const el = sum - arr[i]; // 목표값을 만들기 위해 필요한 나머지 수
if (map[el]) {
return [map[el], i];
}
map[arr[i]] = i;
}
return [];
};
console.log(twoSum(arr, sum));
console.log(twoSum(arr, 12));
console.log(twoSum(arr, 13));
console.log(twoSum(arr, 14));
console.log(twoSum(arr, 24));
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[ 2, 5 ] [ 1, 2 ] [ 1, 3 ] [ 3, 6 ] []
목표값이 10일 경우 인덱스 2의 7과 인덱스 5의 3을 더하면 10이 되어 [2, 5]가 반환됩니다. 반면 목표값 24는 배열 내 어떤 두 수의 합으로도 만들 수 없으므로 빈 배열이 반환됩니다.
알아두면 좋은 팁
위 코드에서는 if (map[el])처럼 값을 진릿값으로 확인하는데, 필요한 수가 인덱스 0에 저장된 경우 0은 falsy로 평가되어 해당 쌍을 건너뛸 수 있습니다. 이러한 엣지 케이스를 방지하려면 if (el in map) 또는 if (map[el] !== undefined)로 존재 여부를 확인하는 것이 더 안전합니다.