메뉴 리뉴얼

• 효율적인 방법은 딱히 없다. n이 작으니 주문이 한번 올 때마다, 모든 부분집합을 다 구해서 카운터를 각각 올려주는 무식한 방법으로 해결 가능
  • 모든 요리 조합에 대해서 주문 횟수를 세는 것은 O(n*2^m). (n=주문의 갯수, m=한번 주문에 포함가능한 요리 갯수)
  • 코스의 크기별로 가장 많이 주문된 조합을 찾는 것은, 모든 크기에 대해서 쿼리가 들어온 경우에, 최대로 전체 조합의 갯수만큼 걸린다. 즉, 이것도 역시 O(n*2^m).
• itertools.combinations와 collections.Counter가 유용하게 쓰인다
• 하지만, 그래도 이것저것 구현에 신경써야 하는 사소한 것들이 많다.

"""Solution code for "Programmers 72411. 메뉴 리뉴얼".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/72411
- Solution link: http://www.teferi.net/ps/problems/programmers/72411
"""

import collections
import itertools

MAX_MENU_COUNT = 10


def solution(orders, course):
    counter_by_size = [collections.Counter() for _ in range(MAX_MENU_COUNT + 1)]
    for order in orders:
        for i in range(2, len(order) + 1):
            counter_by_size[i].update(itertools.combinations(sorted(order), i))

    answer = []
    for menu_count in course:
        menus_and_count = counter_by_size[menu_count].most_common()
        if menus_and_count and (max_count := menus_and_count[0][1]) >= 2:
            for m, c in menus_and_count:
                if c != max_count:
                    break
                answer.append(''.join(m))

    return sorted(answer)