[PG/Python] 메뉴 리뉴얼

📌 문제

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

코딩테스트 연습 - 메뉴 리뉴얼

 

📌 문제 접근 방법

1. orders를 문자열의 길이로 내림차순 정렬, course를 오름차순 정렬한다.
   (코스에 들어갈 메뉴의 개수보다 order의 길이가 작으면 필요없기 때문에 pop을 하기 위해 사전 처리)
2. course를 순회하며 코스에 들어갈 메뉴 개수를 정하고 원하는 개수보다 적은 개수의 메뉴를 주문한 경우는 제외하기 위해 pop해준다.
3. 각 주문에 대해 combination을 사용해서 만들 수 있는 조합들의 개수를 모두 센다.
4. 조합들 중 카운팅 개수가 가장 큰 것들을 answer에 append 한다.
5. answer를 정렬하여 반환한다.

 

📌 코드

# 프로그래머스 메뉴 리뉴얼

from collections import defaultdict
from itertools import combinations

def solution(orders, course):
    orders.sort(key=lambda x: -len(x))
    course.sort()

    answer = []
    for cnt in course:
        while orders and len(orders[-1]) < cnt:
            orders.pop()
        
        menus = defaultdict(int)
        for order in orders:
            for combo in combinations(order, cnt):
                combo = sorted(list(combo))
                menus[''.join(combo)] += 1

        result = sorted(menus.items(), key=lambda x: -x[1])
        
        i = 0
        while i < len(result) and result[0][1] >= 2 and result[i][1] == result[0][1]:
            answer.append(result[i][0])
            i += 1
    
    return sorted(answer)