[JS] 2021카카오 : 메뉴 리뉴얼 프로그래머스 LEVEL2

---

문제 링크

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

풀이 전략

기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.
또한 최소, 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.

정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 return 해주세요.
배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 합니다.

인자로 주어지는 orders와 course의 크기가 크지 않은 점을 감안하여 조합, dfs로 풀어야겠다 생각하였다. 모든 경우의 수를 Map에 담아 주어 이 것을 가지고 풀면되겠다 생각하였다. 

코드 

const t1 = ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"];
const t1_2 = [2, 3, 4];
const t2 = ["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"];
const t2_2 = [2, 3, 5];
const t3 = ["XYZ", "XWY", "WXA"];
const t3_2 = [2, 3, 4];

console.log(solution(t1, t1_2));
console.log(solution(t2, t2_2));
console.log(solution(t3, t3_2));

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

    for (let i = 0; i < course.length; i++) {
        let myHm = new Map();
        for (let j = 0; j < orders.length; j++) {
            const arr = combi(orders[j], course[i]);

            for (const elem of arr) {
                if (myHm.has(elem)) myHm.set(elem, myHm.get(elem) + 1);
                else myHm.set(elem, 1);
            }
        }
        myHm = [...myHm.entries()]
            .filter((val) => val[1] > 1)
            .sort((a, b) => b[1] - a[1]);

        if (!myHm.length) continue;
        const max = myHm[0][1];
        myHm.forEach(([str, num]) => {
            if (max === num) answer.push(str);
            else return;
        });
    }

    return answer.sort();
}

function combi(str, num) {
    const arr = [];
    const ch = Array.from({ length: str.length }, () => 0);
    const tmp = Array.from({ length: num });

    dfs(0, 0);
    function dfs(L, s) {
        if (L === num) {
            const cpy = tmp.slice();
            arr.push(cpy.sort().join(""));
        } else {
            for (let i = s; i < str.length; i++) {
                if (ch[i] === 0) {
                    ch[i] = 1;
                    tmp[L] = str[i];
                    dfs(L + 1, i + 1);
                    ch[i] = 0;
                }
            }
        }
    }
    return arr;
}

 

회고

그저 배운 것들을 응용하여 풀면되었다. 복잡하게 생각하면 어려워져서 힘들었다. 이때 주의 할 점은. dfs로 tmp에 있는 값을 sort하여 arr에 넘겨 주었는데 이때 cpy를 만들지 않으면 tmp에 있는 배열이 그대로 적용되어 값이 이상하게 꼬일 수 있다. 그래서 새로운 cpy배열을 얕은복사하여 원본 tmp가 훼손되지 않게 하였다. 

 

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)