[프로그래머스] 메뉴 리뉴얼 (2021 KAKAO BLIND) / python

1. 문제 설명

 

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

어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는
이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.

단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다.
또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만

코스요리 메뉴 후보에 포함하기로 했습니다.

예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면,
(각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)

 

손님 번호 주문한 단품메뉴 조합

1번 손님	A, B, C, F, G
2번 손님	A, C
3번 손님	C, D, E
4번 손님	A, C, D, E
5번 손님	B, C, F, G
6번 손님	A, C, D, E, H

 

가장 많이 함께 주문된 단품메뉴 조합에 따라 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.

 

코스 종류 메뉴 구성 설명

요리 2개 코스	A, C	1번, 2번, 4번, 6번 손님으로부터 총 4번 주문됐습니다.
요리 3개 코스	C, D, E	3번, 4번, 6번 손님으로부터 총 3번 주문됐습니다.
요리 4개 코스	B, C, F, G	1번, 5번 손님으로부터 총 2번 주문됐습니다.
요리 4개 코스	A, C, D, E	4번, 6번 손님으로부터 총 2번 주문됐습니다.

 

[문제]

각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders,
"스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가

매개변수로 주어질 때,
"스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록

solution 함수를 완성해 주세요.

 

2. 풀이 전 계획과 생각

입력

• orders → 각 손님들이 주문한 단품메뉴들
• course → "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열

 

구하고자 하는 바

새로 추가하게 될 코스요리의 메뉴 구성 (사전 순으로 오름차순 정렬)

⇒ Key : 단품메뉴 Value : 빈도수

⇒ 정렬해주고 Key, Value를 매핑해주는 HashMap을 사용하자.

 

행위의 규칙성, 패턴 파악

각 orders마다 course만큼 뽑아와서 Key값으로 추가하고 Value를 넣는다.

20 * (10C2 + 10C3 + 10C4 ... + 10C10) + 정렬

N + N log N (N = 20 * (10C2 + 10C3 + 10C4 ... + 10C10) = 20 * 2 ^ 10 )

= N ( 1 + log N)

= 20 * 10 ^ 3 * 5 이하

= 10 ^ 5 이하

 

필요한 로직

각 orders의 element만큼 course 만큼 뽑아서 HashMap에 추가한다.

하나의 key값 자체가 사전순으로 오름차순이여야 하고 순서가 달라도 같은 처리를 해주기 위해, order를 정렬해준다.

key가 사전순으로 오름차순이여야 하므로 마지막에 answer를 정렬한다.

 

3. 풀이하면서 막혔던 점과 고민

🤔 HashMap으로부터 각자의 course의 길이 중에 가장 큰 값의 key를 가져오려면,

     HashMap을 어떻게 저장할까? or HashMap으로부터 어떻게 가져올까?

 

단품메뉴들의 갯수마다 빈도수가 높은 값을 가져와야 하므로, 단품메뉴들의 갯수(= 길이)마다 처리해주자.

전체 모든 조합을 구하지 말고 각자의 단품메뉴들의 갯수(= 길이)마다,
조합을 구하고 바로 가장 큰 값을 가져온다.

 

4. 풀이

hash_map = dict()
selected = []

def get_max_course():
    global hash_map
    result = []
    
    sorted_hash_map = sorted(hash_map.items(), key = lambda x: x[1], reverse = True)
    
    max_value = 2
    for key, value in sorted_hash_map:
        if value >= max_value:
            result.append(key)
            max_value = value
    
    return result

def combination(current_idx, order, length):
    global hash_map, selected
    
    if current_idx >= len(order):
        if len(selected) == length:
            key = ''.join(selected)

            if key not in hash_map:
                hash_map[key] = 1
            else:
                hash_map[key] += 1

        return
    
    selected.append(order[current_idx])
    combination(current_idx + 1, order, length)
    selected.pop()
    combination(current_idx + 1, order, length)
    

def solution(orders, course):
    global hash_map
    
    answer = []
    for length in course:
        hash_map = dict()
        for order in orders:
            order = sorted(list(order))
            
            combination(0, order, length)
        
        answer += get_max_course()
    return sorted(answer)

 

5. 다른 풀이 - Itertools, Counter Library

from itertools import combinations
from collections import Counter

def solution(orders, course):
    answer = []

    for length in course:
        # 해당 길이의 combination 구하기
        total_combination = []
        for order in orders:
            combination = combinations(sorted(order), length)
            total_combination += combination

        # 해당 길이의 조합에 대한 count의 큰 값을 구하고, 해당 key를 구하기
        counter = Counter(total_combination)
        if len(counter) != 0 and max(counter.values()) != 1:
            for key in counter:
                if counter[key] == max(counter.values()):
                    answer += [''.join(key) ]

    return sorted(answer)

 

6. 풀이 후 알게된 개념과 소감

• 특정 기준 순으로 처리해주고 싶다면 특정 기준마다 각각의 로직을 처리해주자.