메뉴 리뉴얼

2021 KAKAO BLIND RECRUITMENT

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

프로그래머스

소요 시간 : 45분

실행 결과 : 성공

---

아마 다양한 테스트 케이스가 주어지지 않는다면 성공하지 못했을 것이다.

문제를 잘 이해해야하고, 문제를 잘 읽어보아야한다. 문자열의 정렬조건, 조합을 언제 사용해야하는지 등등...

 

먼저 입력값으로 주어진 course를 순회한다. course는 코스요리를 구성하는 메뉴의 갯수를 표현하는 것으로 이 값을 조합에서 뽑는 갯수로 사용해야한다.

course.forEach(num) :
  num // 코스요리에 포함할 요리의 갯수
  orders.forEach(order) :
    // 각 손님들이 주문한 단품메뉴 중에 num개를 뽑아 조합의 경우를 구한다.
    // 구한 조합의 경우에서 해당 조합을 몇 명이 뽑았는지 카운팅한다.
      // 단, 주의할 점이 있다. 'AB'랑 'BA'는 같은 메뉴의 조합이다.
    // 문제의 조건에 맞게 2명 이상 주문한 경우만 고려해야한다. 2명 이상 카운팅된 조합만 후보메뉴가 된다.
    // 후보메뉴들 중, 가장 많이 뽑힌 메뉴를 골라 ret 배열에 넣어준다.
    ...
    // ret 배열은 문제의 조건에 맞게 정렬한다. ret 배열의 요소도 정렬되어야한다.

 

구현

let table;

function solution(orders, course) {
    // orders를 정렬하는 이유는 같은 메뉴의 조합에 대해 다르게 카운팅하는 것을 막기 위해서다.
    orders = orders.map((str)=> [...str].sort().join(""));
    const ret = [];
    for(const num of course){
        table = new Map();
        orders.forEach((order)=>{
            if(order.length >= num) combi(-1, [], order, num);
        });
        // 만약 2명 이상 주문한 조합의 메뉴가 아니라면 제거한다. 후보메뉴 필터링
        for(const key of table.keys()){
            if(table.get(key) < 2) table.delete(key);
        }
        let max = Math.max(...[...table.values()]);
        for(const key of table.keys()){
            if(table.get(key) === max) ret.push(key); // 가장 많이 주문한 조합을 결과 배열에 넣어준다.
        }
    }
    return ret.map((elem)=> [...elem].sort().join("")).sort((a, b)=>{
        if(a > b) return 1;
        else if(a < b) return -1;
        return 0;
    });
}

function combi(start, b, order, r){
    if(b.length === r){
        const key = b.join("");
        if(table.has(key)) table.set(key, table.get(key) + 1);
        else table.set(key, 1);
    }
    else{
        for(let i = start + 1; i < order.length; i++){
            b.push(order[i]);
            combi(i, b, order, r);
            b.pop();
        }
    }
}