[Level 2] 메뉴 리뉴얼

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

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

---

접근

딕셔너리를 활용하였다. 먼저 각 손님들이 주문한 메뉴를 통해 만들 수 있는 코스 조합을 생성한다. 이 때 코스에 포함되는 메뉴의 수가 주어지기 때문에 해당 수만큼 메뉴가 포함된 조합을 생성한다. 이후 생성된 코스 조합을 딕셔너리에 key로 저장하고 value에는 해당 코스 조합의 개수를 저장한다.

이제 course의 들어있는 코스에 포함된 메뉴의 개수들 중 최댓값을 갖는 코스들을 answer에 추가한다.

 

구현

- 먼저 각 사람들이 주문한 메뉴를 통해 조합을 구한다.

- 이때 사람들이 주문한 메뉴들을 오름차순으로 정렬한다. 왜냐하면 A, B를 주문한 손님과 B, A를 주문한 손님이 있을 때 AB로 시킨 것으로 카운트 되어야하기 때문이다.

- 이제 각 코스들의 개수를 course_dict에 저장한다. 

course_dict = dict()
    for order in orders:
        order_list = sorted(list(order))
        for k in course:
            combi = list(combinations(order_list, k))
            for c in combi:
                c = ''.join(c)
                if c in course_dict:
                    course_dict[c] += 1
                else:
                    course_dict[c] = 1

- 이제 딕셔너리를 탐색해 원하는 조합에서의 최댓값을 구한다.

- 이후에 코스에 포함되는 메뉴의 개수대로 최댓값을 갖는 코스를 answer에 저장한다. 

- 이때 코스에 포함된 메뉴의 개수가 2이상일 때만 answer에 넣는다.

- 마지막으로 answer을 오름차순으로 정렬한다.

    N = len(course)
    size = [0] * N
    for i in range(N):
        for k, v in course_dict.items():
            if len(k) == course[i]:
                size[i] = max(size[i], v)
    
    for i in range(N):
        for k, v in course_dict.items():
            if len(k) == course[i] and v == size[i] and v >= 2:
                answer.append(k)
    answer = sorted(answer)
    return answer

---

전체 코드

from itertools import combinations
def solution(orders, course):
    answer = []
    course_dict = dict()
    for order in orders:
        order_list = sorted(list(order))
        for k in course:
            combi = list(combinations(order_list, k))
            for c in combi:
                c = ''.join(c)
                if c in course_dict:
                    course_dict[c] += 1
                else:
                    course_dict[c] = 1
                    
    N = len(course)
    size = [0] * N
    for i in range(N):
        for k, v in course_dict.items():
            if len(k) == course[i]:
                size[i] = max(size[i], v)
    
    for i in range(N):
        for k, v in course_dict.items():
            if len(k) == course[i] and v == size[i] and v >= 2:
                answer.append(k)
    answer = sorted(answer)
    return answer