greentea31's Note

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

풀이 과정

비문학 지문을 읽듯이 꼼꼼히 읽지 않으면 문제 이해가 어려울 수도 있었다. 문제 지문이 굉장히 긴데, 요약하자면 orders의 각 원소 order로 course가지 코스 요리를 구성할 때, 가장 많이 함께 주문한 단품 메뉴를 코스요리로 구성하는 경우를 리스트에 담아 출력해주면 된다.

안 그래도 이해하기 어려운데 문제를 요약하니 더욱 이해가 안 간다. 1번 예시를 살펴보자.

orders = ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]에서 1번째 손님이 주문한 ABCFG로 만들 수 있는 코스요리는 다음과 같다.

1. 코스 요리를 2가지 메뉴로 구성할 때

AB, AC, AF, AG, BC, BF, BG, CF, CG, FG

2. 코스 요리를 3가지 메뉴로 구성할 때

ABC, ABF, ABG, ACF, ACG, AFG, BCF, BCG, BFG, CFG

3. 4가지

ABCF, ABCG, ACFG, BCFG

4. 5가지

ABCFG

이렇게 모든 order에 대해 만들 수 있는 코스 요리를 구하고, 가장 많이 함께 주문한 단품 메뉴를 살펴보면 된다. 첫 번째 예시에서는 "ABCDE"에서 AC가 한 번, "AC"에서 AC가 또 한 번, "ACDE"에서 AC가 또 한 번, "ACDEH"에서 AC가 또 한번 나오면서 AC가 함께 주문된 경우가 4번이 된다. 2가지 메뉴로 코스요리를 만들 때, 4번보다 같거나 많이 나오는 경우는 없으므로 답에는 AC가 포함되고, AC를 제외한 다른 2가지 메뉴 코스요리는 답에 포함되지 않는다 (가장 많이 함께 주문된 단품 메뉴가 아닌 것이 되므로)

XW, WX등은 같은 코스요리로 처리하기 위해 적절히 sort()를 활용해주고, 가장 많이 함께 주문한 단품 메뉴 구성 이어도 2번 이상 등장하지 않으면 답에 포함되지 않음을 고려해주면서 문제를 해결하였다.

소스 코드

from itertools import combinations

def solution(orders, course):
    answer = []
    length_filter = {}
    for order in orders:
        for i in range(2, len(order) + 1):
            for j in combinations(order, i):
                word = ''.join(sorted(list(j)))
                if word in length_filter:
                    length_filter[word] += 1
                else:
                    length_filter[word] = 1

    length_list = sorted(length_filter.items(), key=lambda x:x[1], reverse=True)
    length_dict = {}

    for tupl in length_list:
        if tupl[1] < 2:
            continue
        length = len(tupl[0])
        if length not in course:
            continue
        if length in length_dict:
            if length_dict[length] == tupl[1]:
                answer.append(tupl[0])
        else:
            length_dict[length] = tupl[1]
            answer.append(tupl[0])

    answer.sort()
    return answer