programmers Level 2 메뉴 리뉴얼

문제

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

걸린 시간

-

풀이

JavaScript

function solution(orders, course) {
    const answer = [];

    for(let i = 0; i < orders.length; i++){
        orders[i] = orders[i].split('').sort().join('');
    }

    const appear = {/*
        key: string,
        value: number
    */};

    const solve = (idx, cour, cur) => {
        // 현재 길이만큼 코스요리 추가
        if(cour.length >= 2){
            const menu = cour.join('');
            if(!appear.hasOwnProperty(menu)) appear[menu] = 0; // appear 대신 cour 써서 삽질함
            appear[menu]++;
        }
        // 재귀 호출
        for(let i = idx; i < orders[cur].length; i++){
            cour.push(orders[cur][i]);
            solve(i+1, cour, cur);
            cour.pop();
        }
    }

    for(let i = 0; i < orders.length; i++){
        solve(0, [], i);
    }

    const best = {/*
        key: number,
        value: string[]
    */};

    for(let c of course){
        let max_cnt = 0;
        for(let menu in appear){
            const cnt = appear[menu];
            if(c !== menu.length) continue;
            if(cnt < 2) continue;
            if(!best.hasOwnProperty(c)) best[c] = [];
            if(cnt > max_cnt){
                best[c] = [];
                max_cnt = cnt;
                best[c].push(menu);
            }
            else if(cnt === max_cnt){
                best[c].push(menu);
            }
        }
    }

    for(let key in best){
        for(let i of best[key]){
            answer.push(i);
        }
    }

    answer.sort();

    return answer;
}

손님이 주문한 요리의 순서는 상관이 없다. 하지만 코스 요리의 등장 횟수를 세기 위해서는 정렬을 한 후 가능한 모든 조합을 백트래킹하여 조사해주면 된다. (answer 배열에 저장된 값 또한 정렬된 문자열이어야 한다는 문제의 조건도 하나의 힌트였던 것 같다.)

문제를 풀며 놓친 조건들

• 가장 많이 함께 주문한 단품메뉴들
• 최소 두 가지 이상의 단품 메뉴의 구성