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

풀이

각 메뉴들을 조합하여 리스트에 저장하고, 각 course 개수의 best like를 구해주면 된다.

코드

from collections import Counter
from collections import defaultdict

import itertools

def solution(orders, course):
    answer = []
    cand_comb_menu = []

    for num in course:
        for order in orders:
            comb_menues = list(itertools.combinations(order, num))

            #AC, AD, AE
            for comb_menu in comb_menues:
                comb_menu = sorted(comb_menu)
                cand_comb_menu.append("".join(comb_menu))

    cand_comb_menu = Counter(cand_comb_menu).most_common()

    best_like_dict = defaultdict(int)

    for course_num in course:
        best_like = 0

        for menu, like in cand_comb_menu:
            if len(menu) == course_num:
                best_like = max(best_like, like)

        best_like_dict[course_num] = best_like

    
    for course_num in course:
        if best_like_dict[course_num] == 0 or best_like_dict[course_num] < 2:
            continue

        for menu, like in cand_comb_menu:
            if len(menu) == course_num and like == best_like_dict[course_num]:
                answer.append(menu)

    print(sorted(answer))
    return sorted(answer)

 

더 짧은 버전

from collections import Counter
from collections import defaultdict

import itertools

def solution(orders, course):
    answer = []
    cand_comb_menu = []

    for num in course:
        comb_menues = []
        
        for order in orders:
            comb_menues += list(itertools.combinations(sorted(order), num))
            
        cand_comb_menu = Counter(comb_menues)
        answer += [''.join(k) for k, v in cand_comb_menu.items() if v == max(cand_comb_menu.values()) and v>1]

    return sorted(answer)

 

 

소감

처음에는 모든 메뉴를 조합하여 완전탐색을 진행했다.

그렇게하면 n은 최대 24, r은 10이 되어 시간초과가 발생했다.

각 메뉴들마다 완전 탐색을 진행하면 n은 최대 10, r은 10이 되어 탐색의 개수가 훨씬 줄어들고,  메뉴 상에 없는 메뉴들은 조합되지 않아 검색의 시간을 줄일 수 있다.