[프로그래머스] 메뉴 리뉴얼 (Javascript)

💡 문제

https://school.programmers.co.kr/learn/courses/30/lessons/72411

문제 설명

---

내 풀이 📝

function solution(orders, course) {
    var map = new Map();
    const res = [];
    const answer = [];
    
    const dfs = (ordersIndex = 0,start = 0, arr = []) => {
        res.push(arr);
        course.forEach((v)=>{
            if(arr.length === v){ // 부분집합의 수가 코스요리 메뉴 개수인 경우
                arr.sort(); // WX, XW인 경우 WX 2개로 count 하기 위해
                map.set(arr.join(''),(map.get(arr.join(''))||0)+1);
            }
        });
      
        for (let i = start; i < orders[ordersIndex].length; i++) {
            dfs(ordersIndex,i + 1, [...arr, orders[ordersIndex][i]]);
        };
    };
    
    for(let i = 0; i < orders.length; i++){
        dfs(i);
    };
    
    let sortedByValueDsc = new Map([...map].sort((a, b) => a[1] - b[1]).reverse()); // value를 기준으로 내림차순 정렬
    
    for(let i = 0; i < course.length; i++){
        var max = 2; // 코스요리 메뉴는 최소 2가지 이상의 메뉴가 있어야 하기 때문에
        for(let value of sortedByValueDsc.entries()){
            if(value[0].length === course[i]){
              // 부분집합의 메뉴 수가 코스유리 메뉴 수와 같은 경우
                if(max <= value[1]){
                    max = value[1];
                    answer.push(value[0]); // 최대값을 answer에 넣어줌
                }
            }
        }
    }
    return answer.sort();
}

완전 주먹구구식으로 풀었다..

풀이 방식은 손님이 주문한 단품 메뉴(ex: "ABCFG")에서 course 배열에 있는 수 만큼(ex: [2,3,5]) 부분집합을 모두 만들어서 (ex: "AB","AC",..."ABC",..."ABCFG") 카운트 했을 때 2개 이상이면서 가장 큰 수인 경우에 answer 배열에 넣어주는 식으로 구했다.

dfs로 모든 부분집합 구하기

const subSets = (arr) => {
  const result = [];
  
  const dfs = (start = 0, subset = []) => {
    result.push(subset);
    
    for(let i = start; i < arr.length; i++){
      dfs(i + 1, [...subset, arr[i]]);
    }
  };
  
  dfs();
  
  return result;
};

다른 사람 풀이

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) => {
    // arr.sort는 기본적으로 사전식 배열
    const sorted = od.split('').sort();
    // 주문한 음식을 사전순으로 배열해서 문자열을 만든다.
    // course에 있는 길이만 만들면 된다.
    course.forEach((len) => {
      createSet(sorted, 0, len, '');
    });
  });

  const launched = Object.keys(candidates).filter(
    (food) => maxNum[food.length] === candidates[food]
  );

  return launched.sort();
}

이게 훨씬 속도가 빠르다.
재귀랑 dfs 공부하자...