이번 글에서는 숫자 배열 arr을 첫 번째 인수로, 숫자 num을 두 번째 인수로 받는 JavaScript 함수를 작성해 보겠습니다.
이 함수의 목표는 배열의 모든 요소를 num개의 그룹에 나누되, 각 그룹의 합이 서로 동일하게 만들 수 있는지 판단하는 것입니다. 가능한 방법이 하나라도 존재하면 true를 반환하고, 존재하지 않으면 false를 반환합니다.
문제 예시
예를 들어 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.
const arr = [4, 6, 3, 3, 7, 4, 1]; const num = 4;
배열 요소의 전체 합은 28이고, 이를 4로 나누면 각 그룹의 목표 합은 7이 됩니다. 실제로 다음과 같이 네 개의 그룹으로 나눌 수 있습니다.
[7], [1, 6], [4, 3], [4, 3]
따라서 이 경우 함수는 true를 반환해야 합니다.
const output = true;
해결 접근 방식
이 문제는 대표적인 백트래킹(Backtracking) 기반 부분집합 합(Subset Sum) 문제입니다. 해결 과정은 다음과 같습니다.
- 배열 전체의 합이
num으로 나누어 떨어지지 않으면 애초에 불가능하므로 즉시false를 반환합니다. - 또한 어떤 요소라도 목표 합(
sum / num)보다 크다면 해당 요소가 어느 그룹에도 들어갈 수 없으므로 역시false를 반환합니다. - 사용된 요소의 인덱스를
Set으로 추적하면서, 목표 합을 채우는 부분집합을 재귀적으로 탐색합니다. - 하나의 그룹이 완성되면 남은 요소로 다음 그룹 탐색을 계속하고, 모든 요소가 사용되면
true를 반환합니다.
구현 코드
const arr = [4, 6, 3, 3, 7, 4, 1];
const num = 4;
const canDivide = (arr = [], num = 1) => {
const sum = arr.reduce((acc, num) => acc + num);
if (sum % num !== 0 || arr.some(num => num > sum / num)) {
return false;
}
const used = new Set();
return (function find(start, target) {
if (used.size === arr.length) {
return true;
}
if (target < 0) {
return false;
}
if (target === 0) {
return find(0, sum / num);
}
for (let i = start; i < arr.length; i++) {
if (!used.has(i)) {
used.add(i);
if (find(i + 1, target - arr[i])) {
return true;
}
used.delete(i);
}
}
return false;
})(0, sum / num);
};
console.log(canDivide(arr, num));코드 단계별 설명
- 1단계: 전체 합이
num으로 나누어 떨어지지 않거나, 목표 합보다 큰 요소가 하나라도 있다면false를 반환합니다. - 2단계: 이미 사용된 숫자를 추적하기 위해
Set(해시셋)을 사용합니다. - 3단계: 각 그룹의 목표 합을 채우기 위한 부분 분할 탐색을 시작합니다.
- 모든 숫자가 사용되었다면 탐색에 성공한 것이므로 종료합니다.
- 부분합이 목표 값을 초과하면 더 이상 탐색하지 않고 백트래킹합니다.
- 하나의 부분집합을 찾았다면, 남은 숫자로 나머지 그룹을 찾는 탐색을 계속 진행합니다.
- 마지막으로 아직 사용하지 않은 모든 숫자를 후보로 시도해 봅니다.
실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
true
이처럼 백트래킹을 활용하면 배열을 합계가 동일한 여러 그룹으로 나눌 수 있는지 효율적으로 판단할 수 있습니다. 다만 이 알고리즘은 최악의 경우 지수 시간 복잡도를 가질 수 있으므로, 입력 배열의 크기가 매우 클 경우 가지치기(pruning) 최적화를 추가로 적용하는 것이 좋습니다.