72411. 메뉴 리뉴얼

프로그래머스 72411번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

코딩테스트 연습 - 메뉴 리뉴얼 | 프로그래머스 스쿨

풀이

아이디어

각 코스 개수별로 가장 많이 주문된 조합을 찾아야 한다. 각 주문에서 가능한 모든 조합을 생성하고 그 조합들의 등장 횟수를 세어주는 방식으로 풀었다.

1단계: 조합 생성 함수 구현

주문 내역에서 특정 개수만큼의 메뉴 조합을 뽑아야 하기 때문에 백트래킹으로 조합을 생성하는 함수를 만들었다.

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에다 조합 개수와 등장 횟수를 저장해줬다.

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보다 작으면 조건을 만족하지 않기 때문에 건너뛴다.

// 최대 주문 조합 구하기
const max = Math.max(...combMap.values());
if (max < 2) continue;
combMap.forEach((count, comb) => {
  if (count === max) answer.push(comb);
});