(kakao) 메뉴 리뉴얼(python)

1. 문제

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

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

 

2. 구현 과정

1) 메뉴 개수를 나타내는 course값이 10 이하이고, 각 단품 메뉴를 나타내는 알파벳이 26개이다.

코스 요리의 메뉴 개수가 2개라 하면, 가능한 경우의 수는 26C2이고, 3개라 하면 가능한 경우의 수는 26C3이다.

=> 26C1, 26C2, 26C3, 26C4,.... 26C10

 

2) 26C1 + 26C2 + 26C3 + ... + 26C26 = 2^26-1인데, 이 문제에선 최대 26C10이므로 약 2000만개 경우의 수가 나온다 => 완전 탐색으로 풀이 가능!!

 

3) 제약 조건1 : 특정 코스 요리를 최소 2명 이상이 주문해야 함 -> 코스요리 별 주문 횟수를 저장해야 함

=> 딕셔너리 사용

 

4) 제약 조건2: 메뉴 개수가 여러개 주어지고, 그 메뉴 개수 별 코스 요리 리스트 & 주문 횟수를 함께 저장해야 함

=> 메뉴 개수 별 딕셔너리를 저장하는 list 생성

=> course_list = [ {} for _ in range(11) ] #course_list[i] : 코스요리의 메뉴가 i개 일 때, key = 코스요리, value = 해당 코스요리가 선택된 개수를 담는 딕셔너리를 저장하는 리스트

 

5) 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아야 하므로 요리 개수 별 max값 하나만 저장할 수 없음. -> 메뉴 개수 별로 가장 큰 주문 횟수를 저장해야 함. 나중에 주문 횟수가 max_cnt값과 같은 대상들을 모두 출력

=> max_cnt = []  #max_cnt[i] : i개 메뉴로 만들 수 있는 코스요리들 중, 가장 많이 주문된 코스요리의 주문 횟수 

 

6) 손님이 주문한 메뉴들로 만들 수 있는 코스 요리 조합을 모두 생성해서 course_list에 요리 코스와 주문 횟수를 저장한다. 이 때 코스 요리 메뉴 개수 별로 가장 큰 주문 횟수를 max_cnt에 저장한다.

모든 경우의 수 중, 메뉴 개수가 course의 원소값인 대상들만 탐색해서 주문 횟수가 max_cnt[원소값]만큼 주문된 코스 요리를 출력한다.

 

3. 실수한 것 & 새로 안 것

-  comb_list = list(map(''.join, combinations(list이름 , 조합 원소 개수)))로 조합 리스트 저장하기

- 딕셔너리는 정렬이나 순서가 없으므로 출력 전에 answer를 정렬해야 함 

 

4. 코드

from itertools import combinations
MAX = 11

def solution(orders, course):
    answer = []
    course_list = [ {} for _ in range(MAX) ] #course_list[i] : 코스요리의 메뉴가 i개 일 때, key = 코스요리, value = 해당 코스요리가 선택된 개수
    max_cnt = [0] * (MAX) #max_cnt[i] : i개 메뉴로 만들 수 있는 코스요리들 중, 가장 많이 주문된 코스요리의 주문 횟수 

    for order in orders:
        order_list = list(order)
        order_list.sort()
        
        #특정 손님이 주문한 음식들로 만들 수 있는 코스 요리 조합 생성
        for menu_cnt in course:
            comb_list = list(map(''.join, combinations(order_list,menu_cnt)))
            for x in comb_list:
                if x in course_list[menu_cnt].keys(): #이미 만들어진 적 있는 코스 요리면, 딕셔너리의 value값 update 
                    course_list[menu_cnt][x] += 1
                else:
                    course_list[menu_cnt][x] = 1
                max_cnt[menu_cnt] = max( max_cnt[menu_cnt], course_list[menu_cnt][x])
    
    #단품 요리 개수가 cnt(course중 한 원소)개 이면서 가장 많이 주문되었던 코스 요리는 answer에 담아서 출력 
    for cnt in course:
        for key in course_list[cnt].keys():
            if max_cnt[cnt] > 1 and course_list[cnt][key] == max_cnt[cnt]:
                answer.append(key)
                
    answer.sort()
    return answer