[ 프로그래머스 / PYTHON ] 메뉴리뉴얼

문제 설명

메뉴 리뉴얼

각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

[입출력 예]

orders	course	result
["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]	[2,3,4]	["AC", "ACDE", "BCFG", "CDE"]
["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"]	[2,3,5]	["ACD", "AD", "ADE", "CD", "XYZ"]
["XYZ", "XWY", "WXA"]	[2,3,4]	["WX", "XY"]

알고리즘

보자마자 교집합, 순열 생각하고 30분만에 풀었는데 틀림

처음 생각
1. 각각의 orders 요소들 set(order)로 문자열을 리스트로
2. 손님마다 교집합 구함
3. course에 해당하는 집합 수면 answer에 추가
4. answer 중복 제거, 정렬

틀린이유

• "만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다."
• 조합 중 가장 많은 개수만 선택.

2번째 예시에서의 결과는 ["ACD", "AD", "ADE", "CD", "XYZ"]

처음한 생각한 대로라면 "ABCDE", "ADE" 의 교집합 = "ADE"가 나와 바로 answer에 추가
하지만 이렇게 되면 "AD"와 "AE" 이 둘의 개수는 세주지 않았음

첫번째 문제 - 조합 중 가장 많은 개수만 생각한 것이아니라 모든 조합을 출력한다는 점이
두번째 문제 - 조합 중 가장 많은 개수만 선택해야할 때 "AD", "AE"와 같은 경우는 개수를 세지 않음

수정한 알고리즘

1. 각각의 orders 요소들 set(order)로 문자열을 리스트로
2. 손님마다 교집합 구함
   3. 교집합의 개수가 course[0]과 같거나 크다면 course 리스트를 돔.
      4. 구한 교집합을 course[i]의 개수만큼 조합하여 딕셔너리에 추가, 이미 있다면 개수를 더해줌
3. 딕셔너리를 집합의 개수(키의 len)과 언급된 개수(valuse)를 기준으로 정렬
   두번째 예제를 기준으로 dic의 구조
   [('AB', 1), ('AE', 1), ('DE', 1), ('AC', 1), ('XY', 1), ('XZ', 1), ('YZ', 1), ('CD', 3), ('AD', 3), ('ADE', 1), ('ACD', 1), ('XYZ', 1)]
4. dic[-1][0]의 길이를 cr(현재보고 있는 코스 메뉴의 개수)로, dic[-1][1] 을 max_값으로 저장
5. 딕셔너리가 빌 때까지 while문
   menu, n = dic.pop()
   if n이 max_의 개수와 같다면 answer에 menu를 추가 아니면 넘어가기.
   elif 메뉴의 개수가 달라진다면 cr과 max값 초기화 해당값 answer에 추가.

코드

from itertools import combinations
def solution(orders, course):
    answer = []
    dic = {}
    for i in range(len(orders)):
        orders[i] = set(orders[i])

    for a,b in combinations(orders,2):
        temp = sorted(list(a&b))
        if len(temp) >= course[0]:
            for c in course:
                for m in combinations(temp,c):
                    menu = ''.join(list(m))
                    if menu in dic:
                        dic[menu] += 1
                    else: dic[menu] = 1
    dic = sorted(dic.items(), key = lambda x: [len(x[0]),x[1]])
    cr =  len(dic[-1][0])
    max_ = dic[-1][1]
    while dic:
        menu, n = dic.pop()
        if len(menu) != cr:
            cr = len(menu)
            max_= n
            answer.append(menu)
        elif n==max_: answer.append(menu)
    return sorted(answer)