숫자로 이루어진 배열을 첫 번째 인수로, 목표 합계(target sum)를 두 번째 인수로 받는 자바스크립트 함수를 작성해야 합니다.
이 함수는 배열 내에서 서로 더했을 때 목표 합계가 되는 두 숫자를 찾아 해당 요소들의 인덱스를 배열 형태로 반환해야 합니다. 이때 두 숫자는 반드시 연속된 요소일 필요는 없습니다.
핵심 조건은 이 작업을 선형 시간(O(n)), 즉 단 한 번의 반복으로 처리해야 한다는 점입니다.
접근 방법: 해시 맵(Map) 활용
선형 시간 안에 문제를 해결하려면 중첩 반복문을 사용하는 브루트 포스 방식 대신 Map 객체를 활용하는 것이 효과적입니다. 동작 원리는 다음과 같습니다.
- 배열을 한 번씩 순회하며 각 숫자를 확인합니다.
- 현재 숫자가 맵에 존재하지 않으면, '목표 합계에서 현재 숫자를 뺀 값'을 키로, 현재 인덱스를 값으로 저장합니다. 즉, 앞으로 만나야 할 '짝꿍 숫자'를 미리 등록해 두는 것입니다.
- 현재 숫자가 이미 맵에 존재한다면, 저장되어 있던 인덱스와 현재 인덱스를 즉시 반환합니다.
이 방식을 사용하면 각 요소를 딱 한 번만 방문하면서도 정답을 찾을 수 있어 전체 시간 복잡도가 O(n)이 됩니다.
예제 코드
const arr = [1, 3, 5, 7, 9, 11];
const target = 16;
const twoSum = function(arr, target) {
const map = new Map();
for(let i = 0; i < arr.length; i++) {
let num = arr[i];
if(map.get(num) === undefined){
map.set(target - num, i)
} else {
return [map.get(num), i]
};
};
};
console.log(twoSum(arr, target));출력 결과
[3, 4]
콘솔에는 위와 같은 결과가 출력됩니다.
동작 과정 상세 분석
왜 [3, 4]가 반환되는지 단계별로 살펴보겠습니다.
- i=0, num=1 → 맵에 없음 → map.set(15, 0) 저장
- i=1, num=3 → 맵에 없음 → map.set(13, 1) 저장
- i=2, num=5 → 맵에 없음 → map.set(11, 2) 저장
- i=3, num=7 → 맵에 없음 → map.set(9, 3) 저장
- i=4, num=9 → 맵에 존재! → return [map.get(9), 4] = [3, 4]
arr[3] = 7, arr[4] = 9이고, 7 + 9 = 16으로 목표 합계와 일치하므로 두 인덱스가 반환됩니다.
복잡도 분석
- 시간 복잡도: O(n) — 배열을 한 번만 순회하며, Map의 get/set 연산은 평균적으로 O(1)입니다.
- 공간 복잡도: O(n) — 최악의 경우 모든 요소가 Map에 저장될 수 있습니다.