문제 정의
주어진 숫자를 특정 규칙에 따라 여러 조각(chunk)으로 나누는 JavaScript 함수를 작성해야 합니다. 이때 반드시 지켜야 할 규칙은 다음과 같습니다.
- 조각(버킷)의 개수는 반드시 2의 거듭제곱이어야 합니다.
- 각 조각에 담기는 항목의 개수 역시 2의 거듭제곱이어야 하며, 최대 크기는 32입니다. 즉, 허용되는 크기는 1, 2, 4, 8, 16, 32뿐입니다.
예제로 이해하기
예를 들어 숫자 8은 다음과 같이 하나의 버킷으로 나눌 수 있습니다.
[8]
숫자 9라면 어떨까요?
[8, 1]
이 경우 두 숫자 모두 2의 거듭제곱이고, 배열의 길이도 2(역시 2의 거듭제곱)이므로 유효한 분할입니다.
이번에는 11을 시도해 보겠습니다.
[8, 2, 1]
안타깝게도 이 방법은 실패합니다. 합계는 11이 맞지만, 배열의 길이가 3으로 2의 거듭제곱이 아니기 때문입니다.
대신 다음과 같이 나누면 어떨까요?
[4, 4, 2, 1]
이 분할은 성공합니다! 요소가 총 4개로 2의 거듭제곱이며, 각 요소의 값도 모두 2의 거듭제곱입니다.
구현 코드
이 문제를 해결하는 코드는 다음과 같습니다.
function permuteCombinations(n, maximum){
const maxPowerOf2 = 1 << maximum;
const m = ~~(n / maxPowerOf2);
const A = new Array(maximum + 1).fill(0);
A[maximum] = m;
let num = n − m * maxPowerOf2;
let p = 0;
let bitCount = 0;
while (num){
if (num & 1){
bitCount += 1;
A[p] = 1;
}
num >>= 1;
p += 1;
}
const min = m + bitCount;
let target = 1;
while (target < min)
target *= 2;
if (target > n)
return −1;
if (target == min)
return A.map((c, p) => [1 << Number(p), c]);
if (target == n)
return [n];
target = target − min;
let i = m ? maximum : p;
while (target && i > 0){
if (!A[i]){
i −= 1;
continue;
}
const max = Math.min(target, A[i]);
A[i] −= max;
A[i−1] += 2*max;
target −= max;
i −= 1;
}
return target ? −1 : A.map((c, p) => [1 << Number(p), c]);
};
console.log(permuteCombinations(11, 5));
알고리즘 동작 원리
이 알고리즘은 크게 세 단계로 동작합니다.
- 최대 크기 우선 배분: 가능한 한 가장 큰 조각(2^maximum)을 최대한 많이 먼저 할당합니다.
- 나머지 처리: 남은 값의 이진수 표현을 활용해 각 자릿수에 해당하는 크기의 조각을 배치합니다.
- 개수 조정: 조각의 총 개수가 2의 거듭제곱이 되도록, 필요하다면 큰 조각 하나를 작은 조각 둘로 분할합니다.
만약 어떤 방식으로도 조건을 만족하는 분할을 찾을 수 없다면 함수는 -1을 반환합니다.
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[ [ 1, 1 ], [ 2, 1 ], [ 4, 2 ], [ 8, 0 ], [ 16, 0 ], [ 32, 0 ] ]
결과의 각 쌍은 [조각 크기, 해당 크기의 조각 개수]를 의미합니다. 즉, 크기가 1인 조각 1개, 크기가 2인 조각 1개, 크기가 4인 조각 2개로 구성됩니다. 전체 합은 1×1 + 1×2 + 2×4 = 11이고, 조각의 총 개수는 1 + 1 + 2 = 4개로 2의 거듭제곱이므로 모든 조건을 만족하는 올바른 분할입니다.