## 🌟 문제
[코딩테스트 연습 - 메뉴 리뉴얼 \| 프로그래머스 스쿨](https://school.programmers.co.kr/learn/courses/30/lessons/72411)
손님들의 주문 내역에서 가장 많이 주문된 메뉴 조합을 찾아 코스요리 후보를 구하는 문제. 코스요리는 최소 2가지 이상의 단품메뉴로 구성되어야 하고, 최소 2명 이상의 손님이 주문한 조합만 후보가 될 수 있다.
## 🌟 풀이
각 코스 개수별로 가장 많이 주문된 조합을 찾아야 한다. 각 주문에서 가능한 모든 조합을 생성하고 그 조합들의 등장 횟수를 세어주는 방식으로 풀었다.
### 1단계: 조합 생성 함수 구현
주문 내역에서 특정 개수만큼의 메뉴 조합을 뽑아야 하기 때문에 백트래킹으로 조합을 생성하는 함수를 만들었다.
```javascript
function getCombinations(arr, cnt) {
const result = [];
function backtrack(start, curr) {
if (curr.length === cnt) {
result.push(curr.join(""));
return;
}
for (let idx = start; idx < arr.length; idx++) {
curr.push(arr[idx]);
backtrack(idx + 1, curr);
curr.pop();
}
}
backtrack(0, []);
return result;
}
```
### 2단계: 조합별 등장 횟수 카운트
각 코스 개수에 대해서 모든 주문에서 조합을 생성하고, Map에다 조합 개수와 드장 횟수를 저장해줬다.
```javascript
for (const cnt of course) {
// 주문에서 나온 조합들 구하기
const combMap = new Map();
for (const order of orders) {
const sortedOrder = order.split("").sort();
const combs = getCombinations(sortedOrder, cnt);
combs.forEach((comb) => {
if (combMap.has(comb)) {
combMap.set(comb, combMap.get(comb) + 1);
} else {
combMap.set(comb, 1);
}
});
}
// ...
}
```
### 3단계: 최대 증장 조합 선택
각 코스 개수별로 가장 많이 등장한 조합을 찾는다.
만약 최대 등장 횟수가 2보다 작으면 조건을 만족하지 않기 때문에 건너뛴다.
```javascript
// 최대 주문 조합 구하기
const max = Math.max(...combMap.values());
if (max < 2) continue;
combMap.forEach((count, comb) => {
if (count === max) answer.push(comb);
});
```