여러 개의 숫자 배열을 입력받아, 각 요소와 요소들의 부분 조합이 전체 배열에서 몇 번 등장했는지를 집계한 빈도 맵(frequency map) 객체를 반환하는 JavaScript 함수를 작성해야 합니다.
문제 이해하기
예를 들어 다음과 같은 배열들이 있다고 가정해 보겠습니다.
const a = [23, 45, 21], b = [45, 23], c = [21, 32], d = [23], e = [32], f = [50, 54];
각 배열에서 만들 수 있는 모든 부분 조합(단일 요소부터 전체 요소 조합까지)을 구한 뒤, 동일한 조합이 여러 배열에서 반복될 경우 그 등장 횟수를 함께 세면 최종 출력은 아래와 같은 형태가 됩니다.
const output = {
"21": 2,
"23": 3,
"32": 2,
"45": 2,
"50": 1,
"54": 1,
"23, 45": 2,
"21, 32": 1,
"50, 54": 1,
// ... 기타 조합들
}
접근 방식
이 문제는 크게 세 단계로 나누어 해결할 수 있습니다.
- 조합 생성 (findMatch): 재귀 함수를 활용해 하나의 배열에서 만들 수 있는 모든 부분 조합을 생성합니다. 각 인덱스마다 현재 요소를 조합에 포함하는 경우와 포함하지 않는 경우를 모두 탐색하는 방식입니다.
- 빈도 집계 (mergeCombination): 생성된 각 조합을 오름차순으로 정렬한 뒤 쉼표로 연결된 문자열 키로 변환하고, 객체에 등장 횟수를 누적합니다.
- 최종 통합 (buildFinalCombinations): 가변 인자(...)로 전달된 모든 배열에 대해 위 과정을 반복 수행하여 하나의 결과 객체를 완성합니다.
예시 코드
전체 구현 코드는 다음과 같습니다.
const a = [23, 45, 21], b = [45, 23], c = [21, 32], d = [23], e = [32], f = [50, 54];
// 한 배열에서 가능한 모든 부분 조합을 재귀적으로 생성
const findMatch = arr => {
let result = [];
const pick = (i, t) => {
if (i === arr.length) {
t.length && result.push(t);
return;
};
pick(i + 1, t.concat(arr[i])); // 현재 요소 포함
pick(i + 1, t); // 현재 요소 제외
};
pick(0, []);
return result;
};
const sorter = (a, b) => a - b;
// 조합을 문자열 키로 변환해 빈도 누적
const mergeCombination = (arr, obj) => {
findMatch(arr.sort(sorter)).forEach(el => {
return obj[el.join(', ')] = (obj[el.join(', ')] || 0) + 1;
});
};
// 여러 배열을 받아 최종 빈도 맵 생성
const buildFinalCombinations = (...arrs) => {
const obj = {};
for (let i = 0; i < arrs.length; i++) {
mergeCombination(arrs[i], obj);
};
return obj;
};
console.log(buildFinalCombinations(a, b, c, d, e, f));
출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
{
'21': 2,
'23': 3,
'32': 2,
'45': 2,
'50': 1,
'54': 1,
'21, 23, 45': 1,
'21, 23': 1,
'21, 45': 1,
'23, 45': 2,
'21, 32': 1,
'50, 54': 1
}
코드 핵심 포인트
findMatch의 재귀 함수pick은 각 인덱스에서 "포함/미포함" 두 갈래로 분기하므로, 길이가 n인 배열에서 최대 2ⁿ − 1개의 비어 있지 않은 조합이 생성됩니다.- 배열을
sorter(a, b) => a - b로 미리 정렬하면[45, 23]과[23, 45]처럼 순서만 다른 조합이 같은 키'23, 45'로 병합되어 올바르게 집계됩니다. (obj[key] || 0) + 1패턴은 해당 키가 처음 등장하면 0에서 시작해 1로 설정하고, 이미 존재하면 기존 값에 1을 더하는 간결한 빈도 누적 방법입니다.
참고로 arr.sort()는 원본 배열 자체를 변경(mutate)하므로, 원본 데이터를 보존해야 하는 상황이라면 [...arr].sort(sorter)처럼 복사본을 정렬하는 것이 안전합니다.