⭐️ [프로그래머스 레벨투] 메뉴 리뉴얼 🍱

🔽 문제 링크

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 테스트케이스는 이런 극단적인 경우의 수를 확인하는 코드로 생각됩니다.