[programmers] 메뉴리뉴얼

문제 링크

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

풀이 방법

1. 우선은 course 리스트에 있는 값(=코스요리 내 단품메뉴의 갯수)마다 구분해서 가장 많이 주문된 조합을 구해야 한다.
2. 조합마다 주문 횟수를 세야 하므로 조합을 key로, 횟수를 value로 하여 딕셔너리로 관리하고자 했다.

따라서 course[i] 값을 인덱스로 하여 그 안에서 딕셔너리로 관리하는, max(course) + 1 길이의 리스트를 만들었다.


이후 조합을 구하는 과정에서는 예를 들어 XY, YX가 같은 조합으로 처리되어야 하므로 course[i] 길이의 조합에 대해 한 번 정렬한 뒤에 딕셔너리에 담아주었다.
각 주문에 대한 조합들을 구해서 딕셔너리에 담은 뒤, 리스트를 순회하며 각 딕셔너리마다 가장 많이 주문된 조합을 answer에 담아주었다.

코드

def solution(orders, course):
    def dfs(now, remaining):
        nonlocal course, menus
        if len(now) in course:
            now = ''.join(map(str, sorted(list(now))))
            if now in menus[len(now)]:
                menus[len(now)][now] += 1
            else:
                menus[len(now)][now] = 1

        for i in range(len(remaining)):
            dfs(now + remaining[i], remaining[i + 1:])

    answer = []
    menus = [{} for _ in range(course[-1] + 1)]

    for order in orders:
        dfs('', order)

    for idx in course:
        max = 0
        max_list = []
        for key, value in menus[idx].items():
            if value == 1:
                continue
            if value > max:
                max = value
                max_list = [key]
            elif value == max:
                max_list.append(key)
        answer += max_list

    return sorted(answer)