[구현] 메뉴 리뉴얼

[ericagong]

⭐ 성찰

1. 조합이나 순열 구할 때, 사전 정렬이 필요한지 꼭 점검하기 💡 단, 이 때, 조합 'AB' = 'BA', 'ABCD' = 'DBAC' 으로 동일해야하므로, 조합을 구하기 전, 반드시 문자열을 정렬 처리 💡
2. DFS로 조합 구할 때는 순열과 다르게 DFS(cnt, startIdx)로 시작 인덱스 필요(이전까지 확인한 부분은 재처리할 필요가 없기 때문)
3. 자료 구조 내 등장 횟수 count시 -> new Map() 사용. map.prototype.set, get, size 활용

❓ 문제 상황

메뉴 리뉴얼

👨‍💻 문제 해결

✅ 1차 풀이: DFS를 통해 조합 도출

1. nCr을 구하기 위해, 각 코스별로 모든 손님의 order를 순회 (코스별로 r 고정)
2. DFS를 통해 각 손님별로 가능한 조합을 구함. ㄴ 💡 단, 이 때, 조합 'AB' = 'BA', 'ABCD' = 'DBAC' 으로 동일해야하므로, 조합을 구하기 전, 반드시 문자열을 정렬 처리 💡
3. 구해진 조합에 대해 가장 큰 수를 갖는 조합/ 조합 배열을 추출하여 메뉴 리뉴얼 후보군에 추가
4. 후보군을 유니코드 사전 순으로 정렬해 반환

   
   // https://school.programmers.co.kr/learn/courses/30/lessons/72411?language=javascript

let select = ""; const comb = new Map();

// 가능한 모든 조합 구하기 function DFS(order, r, cnt, startIdx) { if (cnt === r) { comb.set(select, comb.get(select) + 1 || 1); return; } for (let i = startIdx; i < order.length; i++) { select += order[i]; DFS(order, r, cnt + 1, i + 1); select = select.slice(0, select.length - 1); } }

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

course.forEach((r) => { orders.forEach((order) => { order = Array.from(order).sort().join(""); // AB BA는 같으므로 정렬한 뒤 조합 구하도록 처리 DFS(order, r, 0, 0); });

let max_order = -Infinity;
let temp = [];

// 가장 많은 손님들이 시킨 조합을 추출
for (let [key, value] of comb.entries()) {
  if (value < 2) continue;
  if (max_order === value) temp.push(key);
  else if (max_order < value) {
    max_order = value;
    temp = [key];
  }
}

candidates.push(...temp);
comb.clear();

});

// 유니코드 사전 순으로 정렬해 반환 return candidates.sort(); }

### ✅ 2차 풀이: DFS를 통해 조합 도출
- 가독성을 위해 메소드 분리
```javscript
function dfs(comb, lastIdx, cnt, word, dict) {
    if(cnt === comb.length) {
        dict.set(comb, dict.get(comb) + 1 || 1)
        return
    }
    for(let i = lastIdx; i < word.length; i++) {
        comb += word[i]
        dfs(comb, i + 1, cnt, word, dict)
        comb = comb.slice(0, comb.length - 1)
    }
}

function getCourses(dict) {
    let max = -Infinity
    for(let cnt of dict.values()) {
        max = Math.max(max, cnt)
    }

    if(max === 1) return []

    const courses = []
    for(let [course, cnt] of dict.entries()) {
        if(cnt === max) courses.push(course)
    }

    return courses
}

function solution(orders, course, result) {
    const courses = []
    course.forEach((cnt) => {
        let dict = new Map()
        orders.forEach((order) => {
            const word = order.split('').sort()
            let comb = ''
            dfs(comb, 0, cnt, word, dict)
        })

        courses.push(...getCourses(dict))
    })   

    return courses.sort()
}