[알고리즘] 프로그래머스 Lv2 메뉴리뉴얼

문제

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

풀이

단품메뉴 조합과 필요한 코스 요리 메뉴 수가 주어진다.

1. 단품메뉴 주문 내역에서 나올 수 있는 메뉴 조합을 모두 구하면서, 각각 몇번 나오는지 체크해준다. (딕셔너리 자료형 + combination 내장함수 사용) -> my_dict
   이때, AB, BA는 같은 메뉴 조합인 점이 고려될 수 있도록 한다(sort)

2. 필요한 코스 요리 메뉴 수는 2부터 10 사이이므로 미리 숫자 2를 원소로 가지는 길이가 9인 배열 counts를 만든다.

3. 위에서 조합이 나오는 횟수를 체크한 딕셔너리 자료(my_dict)를 반복문에 넣고 조회하면서 (메뉴 개수 - 2)에 해당하는 배열의 수보다 작으면 패스, 크면 result에 리스트 형태로 추가, 같으면 result의 리스트에 추가하는 식으로 result 딕셔너리를 만든다

4. result의 values를 순회하면서 answer에 추가한다

반복문이 워낙 많이 사용되어서 효율은 좋지 않을 것 같다
그러나 문제에서 메뉴는 알파벳으로 주어지고 한 사람이 주문한 메뉴의 수는 10을 넘지 않으며, 주어지는 메뉴 조합의 수는 20을 넘지 않고, 필요한 메뉴의 수는 10이하라고 되어 있어서 반복문을 여러 번 사용해도 될 것이라 생각하고 일단 구현에 초점을 맞추고 풀이했다.

코드

from itertools import combinations

def solution(orders, course):
    my_dict = {} # 메뉴 조합 별 주문 횟수 체크
    counts = [2] * 9 # 코스메뉴 갯수 별 주문 횟수 체크
    result = {} # 정답을 담을 딕셔너리
    for order in orders:
        for n in course:
            result[n] = []
            combs = list(map(''.join, combinations(order, n)))
            for comb in combs:
                comb = ''.join(sorted(comb))
                my_dict[comb] = my_dict.get(comb, 0) + 1

    for key, value in my_dict.items():
        if value > counts[len(key)-2]:
            result[len(key)] = [key]
            counts[len(key)-2] = value
        elif value == counts[len(key)-2]:
            result[len(key)].append(key)

    # print(my_dict)
    # print(result)

    answer = []
    for res in result.values():
        answer.extend(res)

    return sorted(answer)


orders = ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]
course = [2, 3, 4]

orders = ["XYZ", "XWY", "WXA"]
course = [2]
print(solution(orders, course))