[Programmers] 메뉴 리뉴얼

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

프로그래머스

난이도: Lv. 2

정답률: 50%

권장 시간: 80분

권장 시간 복잡도: O(N*2^M)

 

---

# permutations 또는 combinations 이용할 경우 itertools 임포트
# 순서가 필요한 경우 permutations
# 순서가 필요하지 않은 경우 combinations
from itertools import combinations

def solution(orders, course):
    # 코스요리의 메뉴 구성을 문자열 형태로 담을 배열
    answer = []

    # 조합의 메뉴 수 마다 반복문
    for courseCnt in course:
        # ex. 조합의 메뉴의 수가 2일 때, courseCnt = 2
        dict = {}
        
        # 조합 마다 반목문
        for order in orders:
            # ex. 손님의 주문이 "ABCFG"일 때, order = "ABCFG"
            
            # 손님의 주문에서 메뉴 수가 2개인 모든 조합
            possibleSets = list(map(list,list(combinations(order,courseCnt))))
            # ex. temp = [['A', 'B'], ['A', 'C'], ['A', 'F'], ['A', 'G'], ['B', 'C'],
            #            ['B', 'F'], ['B', 'G'], ['C', 'F'], ['C', 'G'], ['F', 'G']]
            
            # 특정 메뉴 수의 모든 조합을 리스트에서 문자열로 변환
            # 딕셔너리의 키는 불변(immutable)이어야 하는데 리스트는 mutable하기 때문에 문자열로 변환
            for possibleSet in possibleSets:
                # ex. possibleSet = ['A','B']
                
                # 리스트를 오름차순 정렬 후 문자열로 변환
                strSet=''.join(sorted(possibleSet))
                # ex. strSet = "AB"
                print(strSet)
                
                # 딕셔너리의 해당 조합 수만큼 카운트
                if strSet in dict.keys():
                    dict[strSet]+=1
                else:
                    dict[strSet]=1
                    # ex. dict = { "AB" : 1}

        # 딕셔너리에 있는 모든 조합에 대하여,
        # 최소 2명 이상의 손님에게서 주문된 구성된 코스요리 후보 중에서
        # 최대로 많이 시킨 조합일 경우 answer에 append
        for combi in dict.keys():
            if dict and dict[combi] >=2 and dict[combi] == max(dict.values()):
                answer.append(combi)

    # 코스 요리 리스트 또한 오름차순 정렬 후 반환
    return sorted(answer)

 

 

---