풀이 과정
처음에는 각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders를 순회하면서, 각 단품메뉴를 키로 두고, 주문한 손님들의 배열을 값으로 하여 Map 자료 구조에 저장하는 방식을 생각했습니다.
const ordersMap = new Map();
orders.forEach((order, index) => {
const cumtomer = index + 1;
[...order].forEach(menu => {
if(ordersMap.has(menu)) {
ordersMap.set(menu, [...ordersMap.get(menu), cumtomer]);
} else {
ordersMap.set(menu, [cumtomer]);
}
});
});
하지만 ordersMap을 이용하여 메뉴 조합을 구하기 어렵다고 판단하였고 다음과 같은 풀이를 구상했습니다.
- orders를 순회하면서 각 요소(손님이 주문한 단품메뉴)를 오름차순으로 정렬
- 정렬된 단품메뉴의 조합을 구함
- 조합은 "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열
course를 순회하면서 각 요소의 값에 따른 단품메뉴의 조합을 구함 - Map 자료구조를 이용하여 단품메뉴의 조합을 키로 가지고, 주문된 단품메뉴 조합의 갯수를 값에 저장
course의 요소 값에 따라 주문된 단품메뉴 조합의 갯수의 최댓값을 저장하여 코스요리 메뉴 구성 후보에 저장- 최종으로 코스요리 메뉴 구성 후보를 오름차순으로 정렬하는 값을 반환
조합
서로 다른 n개의 물건에서 순서를 생각하지 않고 r개를 선택할 때, 이것을 n개에서 r개를 택하는 조합이라고 합니다.
이 조합의 수를 nCr로 나타낼 수 있습니다.
예를 들어 서로 다른 4개의 요소에서 2개를 선택하는 조합을 ₄C₂로 나타낼 수 있고, 다음과 같은 결과를 얻을 수 있습니다.
Input: [1, 2, 3, 4]
Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]먼저 위의 결과를 얻기위한 코드를 다음과 같이 작성했습니다.
const input = [1, 2, 3, 4];
const output = input.reduce((acc, cur, index, arr) => {
const rest = arr.slice(index + 1);
const combinations = rest.map(combination => [cur, combination]);
acc.push(...combinations);
return acc;
}, [])
console.log(output); // [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]이를 이용하여 배열에서 r개를 택하는 조합을 구하는 함수를 다음과 같이 작성했습니다.
const getCombinaions = (arr, r) => {
// 재귀 탈출 조건
// r이 1이 되면, 모든 배열 요소를 반환
if(r === 1) return arr.map(value => [value]);
// arr를 순회하면서 배열의 모든 요소를 한 번씩 고정하여 조합을 구함
const results = arr.reduce((acc, cur, index, arr) => {
// cur: 고정값
// rest: 고정값의 나머지 배열, rest를 가지고 조합을 구함
const rest = arr.slice(index + 1);
// rest에 대한 조합을 구함
const combinations = getCombinaions(rest, r - 1);
// 조합과 고정값을 붙임
const attached = combinations.map(combination => [cur, ...combination]);
//
acc.push(...attached);
return acc;
}, [])
return results;
}재귀함수 작성 시 탈출 조건을 작성할 때 헤매는데 이번에도 어김없이 잔뜩 헤매다가 다른 분들이 작성한 코드를 참고했습니다.
참고한 코드에서는 forEach가 사용되었습니다.
// 참고한 코드
const getCombinations = function (arr, selectNumber) {
const results = [];
if (selectNumber === 1) return arr.map((el) => [el]);
arr.forEach((fixed, index, origin) => {
const rest = origin.slice(index + 1);
const combinations = getCombinations(rest, selectNumber - 1);
const attached = combinations.map((el) => [fixed, ...el]);
results.push(...attached);
});
return results;
}첫 번째 풀이
// 단품메뉴 조합을 구하는 함수
const getMenuCombinaions = (menus, length) => {
if(length === 1) return menus.map(value => [value]);
const results = menus.reduce((acc, cur, index, arr) => {
const rest = arr.slice(index + 1);
const combinations = getMenuCombinaions(rest, length - 1);
const attached = combinations.map(combination => [cur, ...combination]);
acc.push(...attached);
return acc;
}, [])
return results;
}
function solution(orders, course) {
const candidate = [];
const combinationMap = new Map();
orders.forEach(order => {
// 각 단품 메뉴들을 오름차순으로 정렬
const sortedOrder = [...order].sort();
course.forEach(numberOfMenus => {
// numberOfMenus에 따른 sortedOrder의 조합을 구함
const menuCombinations = getMenuCombinaions(sortedOrder, numberOfMenus);
menuCombinations.forEach(menuCombination => {
// 배열 형태의 조합을 문자열로 변환
const combination = menuCombination.join('');
// combinationMap에 각 조합의 갯수를 저장
combinationMap.set(combination, combinationMap.get(combination) + 1 || 1);
})
})
})
let max = Array.from({length: course.length}, () => 1);
course.forEach((numberOfMenus, index) => {
for (const [key, value] of combinationMap) {
if (numberOfMenus === key.length && max[index] < value) {
max[index] = value;
}
}
for (const [key, value] of combinationMap) {
if (numberOfMenus === key.length && value === max[index] && value > 1) {
candidate.push(key);
}
}
})
return candidate.sort();
}이렇게 풀어도 테스트를 통과하지만 course를 반복적으로 순회하여 아래와 같이 코드를 수정했습니다.
두 번째 풀이
// 단품메뉴 조합을 구하는 함수
const getMenuCombinaions = (menus, length) => {
if(length === 1) return menus.map(value => [value]);
const results = menus.reduce((acc, cur, index, arr) => {
const rest = arr.slice(index + 1);
const combinations = getMenuCombinaions(rest, length - 1);
const attached = combinations.map(combination => [cur, ...combination]);
acc.push(...attached);
return acc;
}, [])
return results;
}
function solution(orders, course) {
const candidate = [];
course.forEach(numberOfMenus => {
// 주문된 단품메뉴 조합의 갯수를 저장할 Map 생성
const combinationMap = new Map();
orders.forEach(order => {
// 각 손님이 주문한 단품메뉴 오름차순으로 정렬
const sortedOrder = [...order].sort();
// numberOfMenus에 따른 단품메뉴의 조합
const menuCombinations = getMenuCombinaions(sortedOrder, numberOfMenus);
menuCombinations.forEach(menuCombination => {
// 배열 형태의 조합을 문자열로 변환
const combination = menuCombination.join('');
// combinationMap에 각 조합의 갯수를 저장
combinationMap.set(combination, combinationMap.get(combination) + 1 || 1);
})
})
// 조합의 갯수 중 최댓값
const max = Math.max(...combinationMap.values());
for (const [combination, count] of combinationMap) {
// 최소 2명 이상의 손님으로부터 주문된 조합이면서, 조합의 갯수가 최댓값인 경우
if (count > 1 && count === max) {
// 코스요리 메뉴 구성 후보에 저장
candidate.push(combination);
}
}
})
return candidate.sort();
}첫 번째 풀이에서 course를 순회하는 코드가 반복적으로 이루어지므로, course를 순회하면서 내부에서 코드를 동작할 수 있도록 수정했습니다.
course의 요소값에 따라 combinationMap을 생성하고, Math.max(...combinationMap.values())를 통해 조합의 갯수 중 최댓값을 구하는 코드가 간결해졌습니다.
마지막으로 combinationMap를 순회하며 조합의 갯수가 최댓값인 경우 코스요리 메뉴 구성 후보에 해당 조합을 저장하는 코드도 보다 간결하게 작성할 수 있습니다.
참고
