문제 개요
첫 번째 인수로 숫자 배열을, 두 번째 인수로 목표 합계(target sum)를 받는 함수를 작성해야 합니다. 함수는 배열을 순회하면서 서로 다른 두 값의 합이 목표 합계와 일치하는 고유한 숫자 쌍을 모두 찾고, 마지막에는 해당 값들이 위치한 인덱스를 모두 더한 결과를 반환해야 합니다. 단, 자기 자신과 자신을 더하는 경우(예: 3 + 3)는 제외합니다.
여기서 "고유한 쌍"이라는 조건이 핵심입니다. 한 번 어떤 쌍에 사용된 값은 다른 쌍에 다시 사용될 수 없으며, 배열에 같은 값이 여러 개 있을 경우에는 아직 사용되지 않은 인덱스 중에서 선택해야 합니다.
예시로 이해하기
배열이 다음과 같다고 가정해 보겠습니다.
const arr = [1, 4, 2, 3, 0, 5];
목표 합계는 다음과 같습니다.
const sum = 7;
합이 7이 되는 숫자 쌍은 다음 두 가지입니다.
4 + 3 = 7
2 + 5 = 7
각 값의 인덱스를 확인하면 다음과 같습니다.
4 → 인덱스 1
2 → 인덱스 2
3 → 인덱스 3
5 → 인덱스 5
따라서 최종 출력은 다음과 같습니다.
1 + 2 + 3 + 5 = 11
구현 코드
const arr = [1, 4, 2, 3, 0, 5];
const findIndexSum = (arr = [], sum = 0) => {
let copy = arr.slice(0);
const used = [];
let index = 0, indexFirst = 0, indexSecond, first, second;
while (indexFirst < copy.length){
indexSecond = indexFirst + 1;
while(indexSecond < copy.length){
first = copy[indexFirst];
second = copy[indexSecond];
if (first + second === sum){
used.push(first, second);
copy = copy.filter(el => first !== el && second !== el);
indexFirst--;
break;
}
indexSecond++;
}
indexFirst++;
}
const indexSum = used.sort().reduce((acc, val, ind) => {
const fromIndex = ind === 0 || val !== used[ind - 1] ? 0 : index + 1;
index = arr.indexOf(val, fromIndex);
return acc + index;
}, 0);
return indexSum;
};
console.log(findIndexSum(arr, 7));
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
11
코드 동작 원리
① 쌍 찾기 단계: 원본 배열을 변경하지 않도록 slice()로 복사본(copy)을 만든 뒤, 이중 while 루프를 돌며 가능한 모든 두 값의 조합을 검사합니다. 두 값의 합이 목표 합계와 일치하면 해당 값들을 used 배열에 기록하고, filter()로 복사본에서 그 값들을 모두 제거합니다. 이 과정 덕분에 같은 값이 여러 쌍에 중복 사용되는 것을 막을 수 있습니다.
② 인덱스 합 계산 단계: used 배열을 오름차순으로 정렬한 후 reduce()를 실행합니다. 각 값의 실제 인덱스는 indexOf()로 찾는데, 배열에 중복 값이 있을 경우를 대비해 fromIndex 변수를 활용해 직전에 찾은 인덱스의 다음 위치부터 검색을 시작합니다. 이렇게 하면 이미 사용된 인덱스를 건너뛰고 올바른 인덱스를 얻을 수 있습니다.
성능 참고: 이 알고리즘은 모든 쌍의 조합을 검사하므로 평균적으로 O(n²)의 시간 복잡도를 가집니다. 배열 크기가 매우 크다면 해시 맵(객체)을 활용한 O(n) 방식을 고려할 수 있지만, 위 코드는 "고유 쌍 처리"와 "중복 인덱스 회피" 로직을 명확하게 보여준다는 장점이 있습니다.