72411: 메뉴 리뉴얼

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

---

1. 문제

• 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.
  기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.
  단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.
  
  
• 예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면,
  (각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)
  
  손님 번호주문한 단품메뉴 조합

  1번 손님	A, B, C, F, G
  2번 손님	A, C
  3번 손님	C, D, E
  4번 손님	A, C, D, E
  5번 손님	B, C, F, G
  6번 손님	A, C, D, E, H

  가장 많이 함께 주문된 단품메뉴 조합에 따라 "스카피"가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.
  코스 종류메뉴 구성설명

  요리 2개 코스	A, C	1번, 2번, 4번, 6번 손님으로부터 총 4번 주문됐습니다.
  요리 3개 코스	C, D, E	3번, 4번, 6번 손님으로부터 총 3번 주문됐습니다.
  요리 4개 코스	B, C, F, G	1번, 5번 손님으로부터 총 2번 주문됐습니다.
  요리 4개 코스	A, C, D, E	4번, 6번 손님으로부터 총 2번 주문됐습니다.

 

---

2. 문제의 조건

• 2 <= orders <= 20
• 2 <= len(orders) <= 10
• 1 <= len(course) <= 10
• 사전 순으로 오름차순 정렬

 

---

3. 문제 접근

• 아이디어
  
  해당 문제는 입력 조건이 작아서 완전탐색으로 풀 수 있다고 생각하였습니다.
  문제 예시를 보면서 느낀 것은 "조합" 문제라는 것입니다.
  DFS로 완전탐색하여 course길이 만큼의 조합을 가져오고 그 조합 중에서 가장 많이 겹치는 조합을 중복 없이 오름차순으로 정렬 하여 반환 하였습니다.

 

---

4. 풀이 방법

• DFS(arr, deapth, items, length)
  현재 dfs 깊이가 조합길이와 같으면 현재의 조합을 반환해줍니다.
  
  "ABCD"가 있을 경우
  A부터 시작합니다.
  A를 arr에 넣고 BCD를 DFS 시킵니다. (그럼 그 다음 재귀에는 B를 넣어서 AB가 됨)
  재귀가 끝나면 AB가 되어있으므로 다시 C를 넣기 위해 pop으로 B를 제거합니다.
• getCombination(items, length)
  나온 DFS중 공백을 제거하고 리스트화 시켜 반환합니다.
• solution
  나올 정답 목록을 중복을 제거하기 위해 set()으로 선언합니다.
  course개 만큼의 조합을 뽑아야하므로 iterator로 반복합니다.
  orders 중 order를 course개 만큼의 모든 조합을 불러옵니다. (이 때, order는 사전순으로 정렬 되어 있어야함)
  만약 해당 조합이 없다면 다음으로 넘어갑니다.
  
  나온 조합 중 가장 많이 중복되어 있는 조합의 개수를 가져옵니다.
  
  만약 조합의 개수가 1이면 다음으로 넘어갑니다.
  
  이제 모든 조합의 수 중 최대 조합의 수와 같으면 정답에 추가합니다.

 

---

5. 소스코드

• https://cjw-git.tistory.com/189

 

---

 

cjw.git@gmail.com