[프로그래머스] 메뉴 리뉴얼 (Python)

풀이

문제를 조합으로 푸는 방식으로 접근했다. orders의 원소의 길이가 최대 10이고, course의 원소의 길이도 최대 10이므로 nCk (n과 k는 1~10)조합의 최대 시간 복잡도는 1억 이하이기 때문에 조합으로 풀 수 있다고 판단했다.

course리스트 안의 숫자 원소는 nCk에서 k라고 생각할 수 있다. 이후 orders리스트안의 주문한 단품메뉴의 모든 조합을 구하여 Dictionary에 저장한다. 그리고Dictionary안에서 손님들이 가장 많이 주문한 메뉴의 조합을 찾은 후 꺼내 정답 리스트에 저장한다. 단, 손님들이 가장 많이 주문한 메뉴의 조합의 수가 1개 이하라면 정답 리스트에 저장하지 않는다. 이러한 풀이방식을 이해했다면 문제를 쉽게 풀 수 있을 것이다.

코드

from itertools import combinations


def solution(orders, course):
    answer = []
    for num in course:
        menu = {}
        for order in orders:
            order = list(order)
            order.sort()
            for comb in combinations(order, num):
                if comb in menu.keys():
                    menu[comb] += 1
                else:
                    menu[comb] = 1
        menu = sorted(menu.items(), key=lambda x: x[1])
        maximum = 0
        while menu:
            now_menu, cnt = menu.pop()
            if cnt <= 1:
                break
            else:
                if cnt >= maximum:
                    maximum = cnt
                    answer.append(''.join(now_menu))
                else:
                    break

    answer.sort()

    return answer