[알고리즘 연습] 프로그래머스 메뉴 리뉴얼 (LEVEL 2, 자바스크립트)

문제

프로그래머스

---

풀이

• 단품 메뉴를 조합한 코스 요리의 개수를 구할 때 편하게 구하기 위해 orders의 모든 원소를 오름차순으로 정렬한다.
• course과 orders를 순회하며 재귀를 통해 정해진 단품 메뉴 개수를 만족하는 코스 요리의 조합을 구한다.
• 정해진 단품 메뉴 개수를 만족하는 코스 요리 중 가장 많이 주문한 것을 선택한다. 이 때 가장 많이 주문한 것이 2개 이상일 수도 있다.
• 가장 많이 주문한 것이 1개 이하일 때는 선택하지 않는다.

소스 코드

function solution(orders, course) {
    const answer = [];
    let result = [];
    const combi = [];
    orders = orders.map((order) => order.split('').sort().join(''));
    
    const dfs = (order, start, idx, cnt) => {
      if (idx === cnt) {
        result[cnt].push(combi.join(''));
          
        return;
      }
      
      for (let i = start; i < order.length; i++) {
        combi.push(order[i]);
        dfs(order, i + 1, idx + 1, cnt);
        combi.pop();
      }
    }
    
    for (const count of course) {
      result[count] = [];
        
      for (const order of orders) {
        dfs(order, 0, 0, count);
      }
    }
    
    for (const count of course) {
      const map = {};
      let max = 0;
      
      for (const str of result[count]) {
        if (map[str]) map[str] += 1;
        else map[str] = 1;
          
        if (map[str] > max) max = map[str];
      }
      
      for (const key of Object.keys(map)) {
        if (map[key] === max && max >= 2) answer.push(key)
      }
    }
    
    return answer.sort();
}