Level 2️⃣ - 메뉴 리뉴얼

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

프로그래머스

 

🚀문제 접근

먼저 이 문제의 요구사항을 빠르게 파악하고, 예외할 부분을 체크하자.

문제의 핵심 요구사항은 가장 많이 함께 주문한 단품메뉴의 조합에 따라 코스요리를 만드는 것이다.

이렇게만 적어두면 무슨 말인지 잘 와닿지가 않는다. 작게 작게 이해해보자.

 

1번 손님 ➡ A,B,C,D,E,F

2번 손님 ➡ B,A,F

3번 손님 ➡ B,A

 

이렇게 손님들이 단품메뉴를 주문했다. 이 메뉴들 중에 함께 주문한 단품메뉴의 조합은 다음과 같다.

B,F ➡ 1번손님, 2번손님

A,F ➡ 1번손님, 2번손님

A,B ➡ 1번손님, 2번손님, 3번손님

 

이 조합중에 가장 많이 함께 주문한 조합은 바로 A,B 단품 조합이다. 그렇다면 요리 2개의 코스요리는 A,B가 되는 것이다.

입력값으로는 스카피가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴의 갯수가 주어진다.

이 말은 만약 스카피가 추가하고 단품메뉴의 갯수가 3이라면 손님들이 가장 많이 함께 주문한 조합의 메뉴 갯수가 3이라는 것이다.

다른 말로 표현하면 각각 손님들이 주문한 단품 메뉴 중 3가지를 뽑아 조합의 경우를 만들고 이들중에 가장 많이 함께 주문한 조합을 구하면 된다는 것이다.

 

예외사항은 코스요리의 갯수는 2개 이상이어야하고 단품메뉴의 조합은 2명 이상의 손님으로부터 주문되야 코스요리의 후보가 될 수 있다.

---

어떻게 구현할 수 있을까?

우선 스카피가 추가하고 싶어하는 단품메뉴의 갯수가 다음과 같이 주어진다고 가정하자.

[2, 3, 4]

그렇다면 2일 때는 각각 손님들이 주문한 단품메뉴 중 2개를 뽑아 조합의 경우의 수를 만든다.

그리고 해시맵을 이용해서 각 조합의 경우의 수를 카운팅한다.

이것도 작게 이해해보자.

 

손님1 ➡ A,B,C,F

손님2 ➡ A,B

손님3 ➡ A,B,F

 

이렇게 주문했을 때 단품 요리 2개로 조합한 코스요리의 후보를 뽑기 위해서 다음과 같은 과정을 거친다.

 

손님1 ➡ AB, AC, AF, BC, BF, CF

손님2 ➡ AB

손님3 ➡ AB, AF, BF

 

이 조합 중에 후보가 될 수 있는 것은 AB, AF, BF인데 그 중 가장 많이 주문한 메뉴의 조합은 AB이기 때문에 AB가 후보에 적합하다.

---

코드

function solution(orders, course) {
    let ret = [];
    let table;
    function combi(start, b, arr, r){
        if(arr.length < r) return;
        if(b.length === r){
            let k = [...b].sort().join("");
            if(table.has(k)) table.set(k, table.get(k)+1);
            else table.set(k, 1);
            return;
        }
        else{
            for(let i = start + 1; i<arr.length; i++){
                b.push(arr[i]);
                combi(i, b, arr, r);
                b.pop();
            }
        }
    }
    course.forEach((num)=>{
        let max = Number.MIN_SAFE_INTEGER;
        let tmp = [];
        table = new Map();
        orders.forEach((order)=>{
            let b = [];
            combi(-1, b, order, num);
        });
        for(const k of table.keys()){
            if(table.get(k) < 2) table.delete(k); 
        }
        max = Math.max(...table.values());
        for(const k of table.keys()){
            if(table.get(k) === max) tmp.push(k);
        }
        if(tmp.length) ret.push(tmp.sort());
    });
    return ret.flat().sort();
}

 

구현과정에서 주의할 부분을 정리하자.

'AB' 랑 'BA' 는 같은 메뉴를 조합한 경우이기 때문에 같은 키값으로 보고 카운팅을 해줘야한다.

그렇기 위해서 table에 카운팅할 때 사전순으로 정렬을 해야한다. 문제에서도 사전순으로 정렬하라고 나와있다.

만일 사전순으로 정렬하지 않는다면 'AB'와 'BA'를 다른 키값으로 인식해서 올바르게 메뉴의 갯수가 카운팅되지 않는다.

 

그리고 sort 메서드는 원본배열을 변형시킨다. 따라서 내가 구현한 코드에서 b를 복사하지 않고 그대로 sort 하게되면 원본배열에 변형이 생기기 때문에 combi 함수에서 b.pop() 하는 과정에서 올바르지 않는 값이 나갈 수 있다.

그렇기 때문에 원본배열을 변형시키지 않도록 복사한 후 정렬해야한다. (이 부분에서 오랫동안 헤맸다...)

부수효과를 일으킬 수 있는 메서드에서는 항상 주의하자.

 

b를 스프레드하지 않고 그대로 정렬을 하면 입출력 3번째 예시에서 XY가 아니라 WY가 계속 출력되는 마법이 벌어진다.

왜냐하면 XW가 정렬된 후 변경되어 WX가 되는데 이때 b를 pop하면 X가 나가버리기 때문이다.

let k = [...b].sort().join("");
let k = b.sort().join(""); // 원본배열에 변형이 일어나 버그 발생