[프로그래머스] 메뉴 리뉴얼 - javascript

📌 문제

https://programmers.co.kr/learn/courses/30/lessons/72411?language=javascript

📌 풀이

function solution(orders, course) {
  let menu = new Map();
  const makeMenu = (menuMap, targetMenu, menuNum, idx, curMenu) => {
    if (curMenu.length === menuNum) {
      let menuStr = curMenu.sort().join('');

      menu.set(menuStr, (menu.get(menuStr) || 0) + 1);
    }
    for (let i = idx; i < targetMenu.length; i++) {
      makeMenu(menuMap, targetMenu, menuNum, i + 1, [...curMenu, targetMenu[i]]);
    }
  };

  orders.map((order) => {
    course.map((courseNum) => makeMenu(menu, order, courseNum, 0, []));
  });
  menu = [...menu.entries()].filter((menuItem) => menuItem[1] > 1);

  let ans = [];

  course.map((courseNum) => {
    let filteredMenu = menu.filter((menuItem) => menuItem[0].length === courseNum).sort((a, b) => b[1] - a[1]);
    let maxCnt = filteredMenu.length ? filteredMenu[0][1] : 0;
    filteredMenu.filter((menuItem) => menuItem[1] === maxCnt).map((menu) => ans.push(menu[0]));
  });

  return ans.sort();
}

✔ 알고리즘 : 구현

✔ 조합을 통해 메뉴를 정하고 그 메뉴를 포함하고 있는 사람 수를 카운팅하여 문제를 풀어야 한다

✔ 메뉴 조합 함수

const makeMenu = (menuMap, targetMenu, menuNum, idx, curMenu) => {
    if (curMenu.length === menuNum) {
      let menuStr = curMenu.sort().join('');

      menu.set(menuStr, (menu.get(menuStr) || 0) + 1);
    }
    for (let i = idx; i < targetMenu.length; i++) {
      makeMenu(menuMap, targetMenu, menuNum, i + 1, [...curMenu, targetMenu[i]]);
    }
  };

✔ 입력조건에 따라 모든 경우를 탐색하더라도 시간초과가 발생하지 않는다.

orders.map((order) => {
    course.map((courseNum) => makeMenu(menu, order, courseNum, 0, []));
  });

✔ 메뉴 조합에서 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합만 가능하므로 Map을 배열화시켜서 filter 한다.

menu = [...menu.entries()].filter((menuItem) => menuItem[1] > 1);

✔ course를 순회하며 courseNum이 조합의 길이인 경우만 1차 filter해주고 횟수를 내림차순으로 정렬하여 max값인지 확인하는 2차 filter을 통해 ans에 넣어준다

course.map((courseNum) => {
    let filteredMenu = menu.filter((menuItem) => menuItem[0].length === courseNum).sort((a, b) => b[1] - a[1]);
    let maxCnt = filteredMenu.length ? filteredMenu[0][1] : 0;
    filteredMenu.filter((menuItem) => menuItem[1] === maxCnt).map((menu) => ans.push(menu[0]));
  });

✔ 난이도 : 프로그래머스 기준 LEVEL 2