[Python] 프로그래머스 - 메뉴 리뉴얼

https://programmers.co.kr/learn/courses/30/lessons/72411?language=python3 

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

# 2021 카카오 블라인드 코딩테스트 문제이다.

 

# 우선 메뉴종류가 A부터 Z까지 26가지이고 course가 10이하이므로 모든 요리를 다 확인한다해도

   26C1 + 26C2 + 26C3 + ... + 26C10 = 10,970,271가지이다.

  따라서 모든 메뉴의 조합을 다 구한 뒤 각 메뉴의 개수를 파악해서 풀어주었다.

 

1. 각 손님이 주문한 단품메뉴 orders배열을 돌며 combination(o, i)를 해준다.

   i는 course배열의 원소로써 단품메뉴 i개로 구성된 코스요리를 구해야 한다.

 

2. 단품메뉴의 조합을 해주면 ('A', 'B'), ('A', 'C', 'D') 이런식으로 나온다. 여기서 알파벳순으로 정렬해준뒤

   메뉴들끼리  붙여서 res에 저장해주면 'AB', 'ACD' 와 같이 저장이 된다.

   res들을 course_dish에 append해준다.

 

3. Counter(couse_dish).most_common()을 해주게 되면 course_dish에 있는 원소들의 갯수를 각각 세준 뒤

   가장 많은 원소부터 정렬해서 반환해준다.

   * 예제 1같은 경우 all_menu에는 i가 4일때 [('BCFG', 2), ('ACDE', 2), ('ABCF', 1), ('ABCG', 1),

      ('ABFG', 1), ('ACFG', 1), ('ACDH', 1), ('ACEH', 1), ('ADEH', 1), ('CDEH', 1)]이 들어온다.

        -> BCFG가 2개, ACDE가 2개 ... CDEH가 1개있다는 뜻이다.

 

4. ans = [[0, 0]]으로 설정해준뒤 all_menu를 돌면서 a[1] (현재 코스요리를 주문한 사람)이 

    ans[0][1]보다 크면 ans = [[a[0], a[1]]로 설정해준다. 

     (가장 많은 사람이 주문한 요리를 찾기위해서)

    a[1]이 ans[0][1]과 같으면 ans에 [a[0], a[1]]을 append해준다.

    예제 3과 같이 가장 많은 사람이 주문한 요리가 2개 이상일 수 있기 때문이다.

 

5. 최종적으로 ans에는 가장 많은 사람이 주문한 요리와 주문한 사람의 수가 들어있는데

   i[1] (주문한 사람)이 1이면 제외해야 되므로 i[1]이 1보다 큰 요리들만 answer에 넣어준다.

   마지막으로 answer을 정렬한 뒤 return해주면 정답!

 

from collections import Counter
from itertools import combinations
def solution(orders, course):
    answer = []

    for i in course:
        course_dish = []
        for o in orders:
            for menu in combinations(o, i):
                # 여기서 sorted(menu)를 해줌으로써 코스요리에 있는 요리들의 알파벳도 정렬이된다. (예제 3)
                res = ''.join(sorted(menu))
                course_dish.append(res)
        all_menu = Counter(course_dish).most_common()
        
        ans = [[0, 0]]
        for a in all_menu:
            if a[1] > ans[0][1]:
                ans = [[a[0], a[1]]]
            elif a[1] == ans[0][1]:
                ans.append([a[0], a[1]])

        for i in ans:
            if i[1] > 1:
                answer.append(i[0])
                
    return sorted(answer)