갑자기 글이 날라갔다.. 후... 나름 또 시간 들여서 쓴 글인데 ... 아무튼 이 문제는 문제를 꼼꼼히 읽어야 했던 그런 문제..
1. 문제 설명
문제
각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
입출력 예시
입출력 예에 대한 설명
입출력 예 #2
AD가 세 번, CD가 세 번, ACD가 두 번, ADE가 두 번, XYZ 가 두 번 주문됐습니다.
요리 5개를 주문한 손님이 1명 있지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 5개로 구성된 코스요리는 새로 추가하지 않습니다.
입출력 예 #3
WX가 두 번, XY가 두 번 주문됐습니다.
3명의 손님 모두 단품메뉴를 3개씩 주문했지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 3개로 구성된 코스요리는 새로 추가하지 않습니다.
또, 단품메뉴를 4개 이상 주문한 손님은 없으므로, 요리 4개로 구성된 코스요리 또한 새로 추가하지 않습니다.
2. 어려웠던 점
1) 문제 잘못이해
나는 처음에 2번 이상 주문했다면 무조건 출력하는 줄 알았다. 하지만 다시 보니, 2번 이상 주문한 건 중에서도 가장 많은 건만 출력하는 것이었다. 예를들어 course가 2일때 2개로 메뉴를 구성할 경우, 가장 주문회수가 많은 메뉴일 경우에만 2를 대표하여 출력하는 것이며 이때 그 회수가 동일한 다른 메뉴가 있을 경우 같이 출력하는 것이다.
2) 조합때문에 헷갈렸다.
나는 분명히 조합을 사용해서 메뉴리스트를 뽑았는데, 같은 조합이 있어서 당황했다... 근데 알고보니 당연한 것
예를들어 ["ABCFG", "AC"] 여기서 course가 2인 메뉴 후보를 뽑는다면 (A,C), (A,C) 가 2개 나올 것이다. 왜냐?! 나는 하나의 원소에서 조합을 돌리고 있기 때문에, 당연한 결과였다. "ABCFG" 돌리고, "AC"돌리게 된다.
그래서 딕셔너리의 key에 추가할때 sorted해서 추가해줘야 한다.
3. 기억해야 할 점
-
조합이나 순열을 사용할때 문제에서 사용하는 리스트나 문자열의 개수를 꼭 확인하자 1억개에 1초라고 생각하고 루프를 얼마나 돌리는지 확인해봐야 한다. 이 문제의 경우 개수가 적어서 얼마든지 사용해도 괜찮았다.
이전에 전화번호 목록에서 개수가 10만개인데 루프를 2번돌려서 시간초과가 발생한 적이 있었다. 꼭 주의하자. -
from collections import defaultdict, Counter 모듈에서 특히 most_common()함수를 알아두자. 파라미터로 원하는 개수를 넣으면, 해당 개수만큼 가장 큰 원소가 출력된다.
4. 풀이
나는 이렇게 풀이했다.
from itertools import combinations
from collections import defaultdict, Counter
def solution(orders, course):
result = []
for i in course:
menu_dict = defaultdict(int)
for order in orders:
for menu in combinations(order, i):
if len(list(filter(lambda x: x in menu, list(order)))) == len(menu):
menu_dict[''.join(sorted(menu))] += 1
count_menu = Counter(menu_dict).most_common()
if count_menu:
max = count_menu[0][1]
for menu_pick, menu_num in count_menu:
if menu_num >= 2 and menu_num == max:
result.append(''.join(menu_pick))
return sorted(result)