1. 요약
-
새로운 메뉴 목록을 만들기위해, 단일 상품들을 조합한다.
- 몇 개로 조합 할 지는 문제에서 주어진다. -
이 때, 다음 조건을 만족해야한다.
-
한 사람당 주문한 단일 상품의 조합을 구하여, 그 중 가장 많이 나타난 조합을 선택한다.
- 최소 두명이상이 선택해야한다.
- 가장 많이 나타난 조합이 다수 일 때, 이들을 모두 선택한다.
-
새로운 메뉴를 만들 때, 정렬해서 만들어야한다.
2. 알고리즘
입력 값: orders, course 출력 값: 가장 많이 선택된 메뉴의 조합을 정렬한 리스트
1. answer을 빈 리스트로 초기화한다.
2. 주어진 course에 대해 3.~8.를 수행한다.
3. orders의 원소들 중 가장 긴 문자열이 현재 주어진 course의 원소(조합을 해야하는 수)
보다 작으면 1.로 돌아간다.
4. course_menu를 빈 리스트로 초기화한다.
5. 주어진 orders에 대해 6.~7.를 수행한다.
6. 현재 주어진 orders의 원소(한 사람이 시킨 주문 리스트)를 정렬하고, 조합을 구한다.
7. 5.에서 얻은 조합을 course_menu에 저장한다.
8. course_menu에서 가장 많이 나타난 조합(최소 2명이상 선택) 또는 조합들을 answer에 추가한다.
9. answer를 정렬하고 반환한다.3. 코드
- 조합을 구할 때, 완전탐색으로 구하면 된다.
- 8.을 구할 때,
set을 이용하였다.
course_menu = []
tmp = []
def combination(k, order, m):
global tmp, course_menu
if len(tmp) == m:
menus = ''
for item in tmp: menus += item
course_menu.append(menus)
return
for i in range(k, len(order)):
tmp.append(order[i])
combination(i+1, order, m)
tmp.pop()
def order_sort(order):
tmp = list(order)
tmp.sort()
return ''.join(tmp)
def solution(orders, course):
global course_menu
answer = []
for m in course:
max_length = 0
for order in orders:
order_len = len(order)
if max_length < order_len: max_length = order_len
if max_length < m: continue
course_menu = []
for order in orders:
order = order_sort(order)
combination(0, order, m)
course_menu_set = list(set(course_menu))
counts = []
for menu_set in course_menu_set:
cnt = course_menu.count(menu_set)
counts.append(cnt)
big = max(counts)
if big < 2: continue
good_menus = []
for i in range(len(counts)):
if counts[i] == big: good_menus.append(course_menu_set[i])
for menu in good_menus: answer.append(menu)
answer.sort()
return answer
