문제 소개
정수 배열 arr를 첫 번째 인수로, 단일 정수 target을 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다.
배열에 있는 각 정수에는 '+' 또는 '-' 중 하나의 부호를 자유롭게 붙일 수 있습니다. 이때 함수가 해야 할 일은, 각 숫자에 부호를 배치하는 모든 가능한 조합 가운데 배열 전체의 합이 target과 정확히 일치하는 경우가 총 몇 가지인지 세는 것입니다.
예를 들어 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.
const arr = [1, 1, 1, 1, 1]; const target = 3;
그렇다면 기대하는 출력 결과는 다음과 같습니다.
const output = 5;
출력 결과 설명
출력이 5인 이유는 아래 다섯 가지 조합 모두 합이 3이 되기 때문입니다.
-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3
즉, 다섯 개의 숫자 중 어떤 하나에만 '-'를 붙이고 나머지 네 개에는 '+'를 붙이면 항상 5 − 2 = 3이 되므로, 그런 경우가 총 다섯 가지 존재합니다.
접근 방식: 재귀 + 메모이제이션
모든 부호 조합을 일일이 완전 탐색하면 시간 복잡도는 O(2ⁿ)까지 증가할 수 있습니다. 따라서 이 문제는 재귀(Recursion)와 메모이제이션(Memoization)을 활용한 동적 계획법(DP)으로 효율적으로 풀 수 있습니다.
핵심 아이디어는 다음과 같습니다.
- 마지막 인덱스부터 거꾸로 탐색하며, 현재 위치
i와 남은 목표값target의 조합을 키로 하는 맵(map)에 결과를 저장합니다. - 동일한 상태(
i,target)가 다시 등장하면 이미 계산된 값을 즉시 반환하여 중복 연산을 제거합니다. - 각 숫자마다 '+'를 붙이는 경우(
target - arr[i])와 '-'를 붙이는 경우(target + arr[i])를 모두 재귀적으로 탐색한 뒤 두 값을 더합니다. - 배열에 0이 포함된 경우 '+0'과 '-0'이 서로 다른 배치로 간주되므로, 마지막 원소가 0이고 목표값이 0이라면 경우의 수를 2로 반환하는 예외 처리를 추가합니다.
구현 예제
위 접근 방식을 코드로 구현하면 다음과 같습니다.
const arr = [1, 1, 1, 1, 1];
const target = 3;
const waysToSum = (arr = [], target = 1) => {
// 이미 계산된 상태를 저장하기 위한 메모이제이션 맵
const map = {};
const find = (arr, target, i) => {
let val = i + '->' + target;
// 동일한 상태를 이전에 계산했다면 저장된 값 반환
if(map[val] !== undefined){
return map[val];
};
// 배열의 첫 번째 원소까지 도달한 경우(기저 사례)
if(i === 0){
if (target === 0 && arr[0] === 0) { return 2 }
return arr[0] === target || arr[0] === -target ? 1 : 0
};
// 현재 숫자에 '+' 또는 '-'를 붙이는 두 경우를 모두 탐색
map[val] = find(arr, target + arr[i], i - 1) + find(arr, target - arr[i], i - 1);
return map[val]
};
return find(arr, target, arr.length-1)
};
console.log(waysToSum(arr, target));
실행 결과
콘솔에 위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
5
메모이제이션 덕분에 동일한 하위 문제를 반복해서 계산하지 않으므로, 이 풀이는 완전 탐색보다 훨씬 적은 연산으로 정답을 구할 수 있습니다.