[Programmers](Level2) 메뉴 리뉴얼

문제명: 메뉴 리뉴얼

문제설명:

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. (... 생략)

문제풀이

난이도가 꽤 어려워서 Greedy로 풀었다. 객체를 2번이나 만들고 여러번 for문을 돌려서 시간복잡도가 많이 증가했다. (매우 더럽게 짠 것 같다..) 리팩토링 하고 다시 올릴 예정 ㅠ

function solution(orders, course) {
  var answer = [];
  let storageOfOrderMapping = {};

  for (let i = 0; i < course.length; i++) {
    let numOfBranch = course[i];
    for (let j = 0; j < orders.length; j++) {
      let menus = orders[j].split('');
      // 주문받은 메뉴 길이가 선택할 메뉴 갯수보다 작을 경우
      if (menus.length < numOfBranch) continue;
      // 메뉴 갯수로 조합
      const combinationOfMenus = combination(menus, numOfBranch);

      for (let i = 0; i < combinationOfMenus.length; i++) {
        // 조합이 되는 메뉴들
        let combi = combinationOfMenus[i].join('');
        if (!Object.keys(storageOfOrderMapping).includes(combi)) {
          // 객체에 없으면 생성
          storageOfOrderMapping[combi] = 1;
        } else {
          // 있으면 + 1
          storageOfOrderMapping[combi] = storageOfOrderMapping[combi] + 1;
        }
      }
    }
  }

  // 손님이 주문한 메뉴와, 가짓 수
  function combination(menus, num) {
    // 메뉴가 1개만 남았으면 menu를 return
    if (num === 1) return menus.map((menu) => menu);
    let result = [];

    menus.forEach((menu, idx, origin) => {
      const fixed = menu;
      const rest = origin.slice(idx + 1);
      const combinations = combination(rest, num - 1);
      const attached = combinations.map((v) => [fixed, ...v].sort());
      result.push(...attached);
    });
    return result;
  }

  for (let i = 0; i < course.length; i++) {
    let courseNum = course[i];
    let newObj = {};
    // 기존 객체에서 해당하는 부분만 따로 뺄 수 있는 지 없는 지? map으로 가능한 지?
    // 2이하면 저장 안함
    let maxNum = Object.keys(storageOfOrderMapping).reduce(
      (maxNum, cur, idx) => {
        let length = cur.length;
        if (length === courseNum) {
          const key = Object.keys(storageOfOrderMapping)[idx];
          const val = Object.values(storageOfOrderMapping)[idx];

          newObj[key] = val;
          if (maxNum < val) return val;
          else return maxNum;
        }
        return maxNum;
      },
      0
    );
    // 0일 경우 종료
    if (maxNum === 0) break;

    Object.values(newObj).forEach((val, idx) => {
      if (val === maxNum && val >= 2) {
        const target = Object.keys(newObj)[idx];
        answer.push(target);
      }
    });
  }
  // 정답을 사전 순으로 적용 sort()는 code순 정렬
  return answer.sort();
}