알고리즘 문제를 풀다 보면 하나의 배열을 여러 개의 부분 집합으로 나누는 파티션(partition) 문제를 자주 만나게 됩니다. 이번 글에서는 특히 각 부분 집합 안에 동일한 요소가 중복되지 않도록 하면서, 전체 배열을 구성하는 모든 조합을 찾는 방법을 JavaScript 코드와 함께 살펴보겠습니다.
문제 정의
예를 들어 다음과 같은 배열이 있다고 가정해 보겠습니다.
const arr = [A, A, B, B, C, C, D, E];
여기서 우리가 원하는 것은 이 배열의 모든 요소를 사용하여 전체를 이루는 조합을 찾되, 하나의 부분 집합 내에는 같은 문자가 두 번 이상 등장하지 않아야 한다는 조건입니다.
가능한 조합의 예는 다음과 같습니다.
[A, B, C, D, E] [A, B, C]
[A, B, C, D] [A, B, C, E]
[A, B, C] [A, B, C] [D, E]
조건 설명
이 문제에는 몇 가지 중요한 규칙이 있습니다.
1. 순서는 결과에 영향을 주지 않는다
[A, B, C] [A, B, C] [D, E] 와 [A, B, C] [D, E] [A, B, C] 는 부분 집합의 나열 순서만 다를 뿐, 본질적으로 동일한 조합으로 취급합니다.
2. 부분 집합 내부의 순서도 무시한다
예를 들어 [A, B, C] 와 [B, A, C] 는 같은 부분 집합입니다. 즉, 요소의 배치 순서는 고려 대상이 아닙니다.
구현 아이디어
효율적인 접근 방법은 각 문자를 [문자, 남은 개수] 형태의 쌍으로 관리하고, 재귀적으로 각 문자를 기존 조합의 여러 위치에 분산(spread)시키는 것입니다. 이렇게 하면 자연스럽게 각 부분 집합 내 중복을 방지할 수 있습니다.
코드 예제
실제 구현 코드는 다음과 같습니다.
const arr = [['A', 1], ['B', 2], ['C', 3]];
// 현재 문자(arr)를 조합(combination)의 각 위치에 분산시키는 함수
const spread = (arr, ind, combination) => {
if (arr[1] === 0)
return [combination];
if (ind === -1)
return [combination.concat([arr])];
let result = [];
// 현재 위치(ind)의 그룹에 넣을 수 있는 최대 개수만큼 시도
for (let c=1; c<=Math.min(combination[ind][1], arr[1]); c++){
let comb = combination.map(x => x.slice());
if (c == comb[ind][1]){
// 그룹을 통째로 합치는 경우
comb[ind][0] += arr[0];
} else {
// 일부만 옮기고 새 그룹을 생성하는 경우
comb[ind][1] -= c;
comb.push([comb[ind][0] + arr[0], c]);
}
result = result.concat(spread([arr[0], arr[1] - c], ind - 1, comb));
}
// 현재 문자를 이 그룹에 넣지 않고 다음 위치로 넘어가는 경우
let comb = combination.map(x => x.slice());
return result.concat(spread(arr, ind - 1, comb));
};
// 재귀적으로 모든 조합을 생성하는 헬퍼 함수
const helper = arr => {
function inner(ind){
if (ind === 0)
return [[arr[0]]];
const combs = inner(ind - 1);
let result = [];
for (let comb of combs)
result = result.concat(
spread(arr[ind], comb.length - 1, comb));
return result;
}
return inner(arr.length - 1);
};
// 중복을 제거하고 결과를 문자열로 반환하는 함수
const returnPattern = (arr = []) => {
const rs = helper(arr);
const set = new Set();
for (let r of rs){
const _r = JSON.stringify(r);
if (set.has(_r))
console.log('Duplicate: ' + _r);
set.add(_r);
}
let str = '';
for (let r of set)
str += '\n' + r
str += '\n\n';
return str;
};
console.log(returnPattern(arr));
실행 결과
위 코드를 콘솔에서 실행하면 다음과 같은 출력을 확인할 수 있습니다.
[["ABC",1],["BC",1],["C",1]]
[["AB",1],["BC",1],["C",2]]
[["ABC",1],["B",1],["C",2]]
[["AB",1],["B",1],["C",3]]
[["AC",1],["B",1],["BC",1],["C",1]]
[["A",1],["B",1],["BC",1],["C",2]]
[["AC",1],["BC",2]]
[["A",1],["BC",2],["C",1]]
[["AC",1],["B",2],["C",2]]
[["A",1],["B",2],["C",3]]
결과 해석
출력된 각 행은 하나의 유효한 파티션을 나타냅니다. 예를 들어 [["ABC",1],["BC",1],["C",1]] 은 'ABC' 그룹 1개, 'BC' 그룹 1개, 'C' 그룹 1개로 전체를 나누었다는 의미입니다.
이처럼 문자와 개수를 쌍으로 묶어 관리하고 재귀적으로 분산시키는 방식을 사용하면, 각 부분 집합에 중복 요소가 없는 모든 파티션을 체계적으로 생성할 수 있습니다. 또한 Set을 활용해 JSON 문자열화된 결과의 중복을 걸러내면, 순서만 다른 동일한 조합까지 깔끔하게 제거할 수 있습니다.