문제 개요
임의 개수의 숫자(Number 타입) 인수를 받아, 각 숫자 사이에 더하기(+) 또는 빼기(−) 연산자를 배치할 수 있는 모든 가능한 조합을 계산하고, 그 결과 중 0에 가장 가까운 합을 반환하는 JavaScript 함수를 작성해야 합니다.
예시
예를 들어 인수가 1, 2, 3이라면 만들 수 있는 모든 조합은 다음과 같습니다.
1 + 2 + 3 → 6 1 − 2 − 3 → −4 1 + 2 − 3 → 0 1 − 2 + 3 → 2
이 경우 0에 가장 가까운 합은 정확히 0입니다.
접근 방식
모든 조합을 일일이 나열하면 숫자가 n개일 때 최대 2n−1가지 경우가 발생하여 매우 비효율적입니다. 대신 Set 자료구조를 활용해 지금까지 만들 수 있는 부분 합의 절대값만 저장하면 중복을 제거하면서 효율적으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
- 첫 번째 숫자의 절대값으로 Set을 초기화합니다.
- 이후 각 숫자를 순회하며, 기존 부분합에서 해당 숫자를 더한 값과 뺀 값의 절대값을 새로운 Set에 추가합니다.
- 중간 결과의 부호는 이후 연산 결과의 절대값에 영향을 주지 않으므로(Math.abs 처리), 절대값만 관리해도 최종 답에는 지장이 없습니다.
- 마지막에 Set에 남아 있는 값 중 최솟값이 곧 0에 가장 가까운 합입니다.
코드 구현
const findSmallestPositive = (...arr) => {
let set = new Set([Math.abs(arr[0])]);
for (let i = 1; i < arr.length; i++){
const secondSet = new Set;
for (let d of Array.from(set)){
secondSet.add(Math.abs(d + arr[i]))
secondSet.add(Math.abs(d - arr[i]))
};
set = secondSet;
};
return Math.min(...Array.from(set))
};
console.log(findSmallestPositive(5,3))
console.log(findSmallestPositive(1,2,3))
console.log(findSmallestPositive(1,2,3,5))
실행 결과
2 0 1
결과 해석
- (5, 3): 가능한 조합은 5+3=8과 5−3=2뿐이므로 최솟값은 2
- (1, 2, 3): 1+2−3=0을 만들 수 있으므로 답은 0
- (1, 2, 3, 5): 전체 합이 홀수(11)라 어떤 조합으로도 0을 만들 수 없으며, 가장 가까운 값은 1
이처럼 Set 기반 접근법은 완전 탐색보다 훨씬 적은 연산으로 정답을 구할 수 있어, 인수 개수가 많아질 때 특히 유용합니다.