⭐️ [프로그래머스 레벨투] 메뉴 리뉴얼 🍱
🔽 문제 링크
https://programmers.co.kr/learn/courses/30/lessons/72411
✍🏼 나의 수도 코드
1) pickBestSeller 함수를 통해 course 배열에 담긴 길이별로 setMenu를 골라낸다.
2) orders 중 selectNum과 길이가 같거나 작은 경우만 남긴다.
3) 각 order에 대해 조합을 만들어 candidateMenu에 저장한다.
4) candidateMenu를 orders와 다시 비교하며 가장 잘 팔린 메뉴들을 골라낸다.
5) 그것들을 모아 finalSetMenu로 리턴한다.
👨🏻💻 나의 문제 풀이
function solution(orders, course) {
let finalSetMenu = [];
function makeCombination (menuArr, selectNum) {
const combinationArr = [];
if(selectNum === 1) {
return menuArr.map((value) => [value]);
}
menuArr.forEach((fixed, index, origin) => {
const rest = origin.slice(index + 1);
const combinations = makeCombination(rest, selectNum - 1);
const attached = combinations.map((combination) => [fixed, ...combination]);
combinationArr.push(...attached);
})
return combinationArr;
}
function pickBestSeller(orders, selectNum){
orders = orders.filter(item => item.length >= selectNum);
let candidateMenu = [];
for(let i = 0; i < orders.length; i++){
let combiArr = makeCombination(orders[i].split(""), selectNum);
candidateMenu = candidateMenu.concat(combiArr);
}
candidateMenu = candidateMenu.map(item => item.sort()).map(item => item.join(""));
candidateMenu = candidateMenu.filter((item, index) => {
return candidateMenu.indexOf(item) === index
}).map(item => item.split(""));
let count = 2;
let bestSeller = [];
candidateMenu.forEach((item) => {
let didYouOrder = [];
for(let i = 0; i < orders.length; i++){
didYouOrder.push(item.every(menu => orders[i].includes(menu)));
}
let howManyPeople = didYouOrder.filter(item => item).length;
if(howManyPeople > count){
count = howManyPeople;
bestSeller = [];
bestSeller.push(item)
} else if(howManyPeople === count) {
bestSeller.push(item)
}
})
finalSetMenu = finalSetMenu.concat(bestSeller);
}
for(let i = 0; i < course.length; i++){
pickBestSeller(orders, course[i]);
}
return finalSetMenu.map(item => item.join("")).sort();
}
👩🏻💻 다른 사람의 코드
function solution(orders, course) {
const ordered = {};
const candidates = {};
const maxNum = Array(10 + 1).fill(0);
const createSet = (arr, start, len, foods) => {
if (len === 0) {
ordered[foods] = (ordered[foods] || 0) + 1;
if (ordered[foods] > 1) candidates[foods] = ordered[foods];
maxNum[foods.length] = Math.max(maxNum[foods.length], ordered[foods]);
return;
}
for (let i = start; i < arr.length; i++) {
createSet(arr, i + 1, len - 1, foods + arr[i]);
}
};
orders.forEach((od) => {
const sorted = od.split('').sort();
course.forEach((len) => {
createSet(sorted, 0, len, '');
});
});
const launched = Object.keys(candidates).filter(
(food) => maxNum[food.length] === candidates[food]
);
return launched.sort();
}
🍯 알게 된 것들
코드로 콤비네이션 구현하기 🍕
const getCombinations = function(arr, selectNumber) {
const results = [];
if(selectNumber === 1) return arr.map((value) => [value]);
arr.forEach((fixed, index, origin) => {
const rest = origin.slice(index + 1);
const combinations = getCombinations(rest, selectNumber - 1);
const attached = combinations.map((combination) => [fixed, ...combination]);
results.push(...attached);
})
return results;
}
- Object.keys 활용하기!
=
와===
절대, 절대, 절대, 절대, 절대 헷갈리지 않기 (메모해놓기엔 아주 기초적인 거지만, 처음에 코드 작성할 때 나도 모르게 실수해놓으면, 이런 실수들이 다시 발견해내기 진짜 어려움....!)- 처음에는 아예 orders에 등장하는 모든 알파벳을 모아서, 해당 알파벳들로 만들 수 있는 모든 조합을 만들고 검토했었는데, 이런 방식으로 접근했더니 시간복잡도가 너무 높아짐! 아래는 내가 참고했던 다른 유저의 조언!
저도 해당 부분에서 한번 미끄러졌습니다.
기본적으로 조합은 고등학교때 배운 공식에 따르면 `C(n, r) = n! / ((n-r)! * r!)` 입니다.
여기서 `alphas`가 한 26종류정도 된다고 하고 그중 10개를 뽑는다면, 계산을 대충 때려보면 조합의 개수는 `5,311,735`개 입니다.
여기서 계산에 문제가 생길 것임을 예상 가능합니다.
이 문제를 회피하기 위해서는 combination개수를 줄이면 됩니다.
만약 `['ABCDEFGHIJKLMN', 'OPQRSTUVWXYZ']`라는 사례가 있다면 `combination(alphas, 10)`로 계산하면 경우의 수가 `5,311,735`개 이지만
이 조합중 `'AO', 'AP', ...`같이 두 주문간 메뉴를 섞는 경우의 수는 0회임을 예상 가능합니다.
따라서 `set(combination('ABCDEFGHIJKLMN', 10)) | set(combination('OPQRSTUVWXYZ', 10))` 이런식으로 두 조합을 만든 후 합치면 많은 경우의 수를 줄일 수 있습니다.
위 사례는 `combination('ABCDEFGHIJKLMN', 10) = C(14, 10) = 1001개`, `combination('OPQRSTUVWXYZ', 10) = C(12, 10) = 66개`로 두 조합간에 중복이 없다고 쳐도 `1067`번의 비교만으로 정답이 나올 것임을 예상 가능합니다.
즉 위 사례에서는 비교 횟수가 `5,311,735`회에서 `1067`회로 줄어듭니다.
아마 해당 13, 14, 15 테스트케이스는 이런 극단적인 경우의 수를 확인하는 코드로 생각됩니다.
Author And Source
이 문제에 관하여(⭐️ [프로그래머스 레벨투] 메뉴 리뉴얼 🍱), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@9rganizedchaos/프로그래머스-레벨투-메뉴-리뉴얼저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)