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

문제 링크

프로그래머스

 

문제 유형

조합 (Lv.2)

 

문제 풀이

orders	course	result
["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]	[2, 3, 4]	["AC", "ACDE", "BCFG", "CDE"]
["XYZ", "XWY", "WXA"]	[2,3,4]	["WX", "XY"]

이 문제는 다음과 같은 방식으로 접근했다.

1. 각 손님들이 주문한 단품메뉴 조합에서 코스요리를 구성할 단품메뉴의 수만큼 뽑아서 만든 조합을 만든다.
2. 각 코스요리 후보 조합을 정렬한다. 테스트 케이스 2를 보면 다음과 같다.
   
   [orders를 각각 2개씩 조합할 경우]
   XYZ => XY, XZ, YZ
   XWY => XW, XY, WY
   WXA => WX, WA, XA
   이때,  XW와 WX는 같은 코스요리 조합으로 봐야하므로 정렬을 해줘야 한다.
   
   
3. 코스 후보 조합 각각을 Map 객체의 key로 저장하고, 해당 조합이 나올 때마다 value의 값을 증가시킨다.
4. 훨씬 더 많이 나온 코스요리 조합을 메뉴로 추가하기 위해 가장 많이 주문된 조합의 주문 횟수를 기록한다.
   
   예를 들어, 위에서 2개짜리 코스요리를 만들 때, AC가 4번, DE가 3번 주문되었다.
   이때, 훨씬 더 많이 주문된 조합을 코스요리로 추가해야 한다.
   
   
5. 주문 횟수가 가장 많은 조합이 최소 2명 이상으로부터 주문되었다면 해당 코스 메뉴를 출력한다.

 

코드

function solution(orders, course) {
    const answer = [];
    let max = 0;
    
    // course[i]개짜리 코스 조합별 메뉴 구성 찾기
    for (let i = 0; i < course.length; i++) {
        let map = new Map(); // [알파벳 조합, 주문된 횟수] 저장하는 Map 객체
        orders.forEach((e) => {
            combination(e.split(""), course[i]).forEach((v) => {
                const sorted = v.split("").sort().join(""); // 'WX', 'XW' 같은걸로 보아야하므로 정렬한다.
                map.set(sorted, (map.get(sorted) || 0) + 1);
                if (max < map.get(sorted)) max = map.get(sorted); // 훨씬 많이 나온 조합으로 메뉴 구성한다.
            })
        })
        
        if (max >= 2) {
            for (let [key, value] of map) {
                if (max === value) answer.push(key);
            }
        }
        max = 0;
    }     
    return answer.sort();
}

// 조합
function combination (arr, selectNum) {
    const result = [];
    
    if (selectNum === 1) return arr.map((value) => [value]); // 1개 조합일 경우, 재귀 종료
    
    arr.forEach((cur, idx, arr) => {
        const rest = arr.slice(idx + 1); // 현재 요소 뒤에 배열
        const combinations = combination(rest, selectNum - 1);
        const attached = combinations.map((combination) => cur +  combination);
        result.push(...attached);
    })
    
    return result;
}