2021 KAKAO BLIND RECRUITMENT 메뉴 리뉴얼 Lv. 2

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/72411

파이썬 소스: https://bit.ly/3JGBTCG

 

이 문제를 풀이하는데 놓치기 쉬운 부분이 아래 문장입니다.

만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다.

위의 문장의 의미를 잘 이해하려면, 입출력 예 #2번의 결과를 잘 살펴보아야 합니다.

AD가 세번, CD가 세번 주문 되었습니다. 그리고 AB도 두번 주문 되었습니다.

하지만, 함께 주문된 2개의 메뉴중에서, 가장 많이 주문된 횟수는 세번입니다. 따라서, AD, CD만 답에 포함되고, AB는 두번 주문 되었으므로, 답에 포함되지 않습니다.

위의 문제설명을 좀더 쉽게 바꿔 말하면, 함께 주문된 메뉴의 개수가 같은 것 중에서, 가장 많이 함께 주문된 메뉴만 답에 포함된다고 할 수 있습니다.

 

문제에서 주어지는 orders는 스트링을 가지는 리스트 변수입니다.

def solution(orders: List[str], course: List[int]):     orders = [list(order) for order in orders]     for order in orders:         order.sort()

변수 order 값이 ABC라고 가정하고, course리스트에 2가 들어 있다면, A, B, C를 가지고 크기 2의 조합을 구해야 합니다. 따라서, 조합을 구하기 쉽도록, 미리 스트링을 리스트로 변환합니다. 조합의 순서도 알파벳순서를 따르기  위해서, sort()를 해주겠습니다.

 

for length in course:     candidate_menus = defaultdict(int)     mx = 0

리스트 course에서 조합의 길이를 하나씩 꺼내면서 루프를 실행합니다.

딕셔너리 candidate_menus는 함께 주문된 메뉴를 키로 사용하고, 함께 주문된 메뉴가 몇번 주문되었는지를 값으로 가지는 딕셔너리입니다.

변수 mx는 함께 주문된 메뉴중에서 가장 많이 주문된 횟수를 저장합니다.

 

for order in orders:     if length <= len(order):         for menu in list(combinations(order, length)):             candidate_menus[tuple(menu)] += 1         mx = max(list(candidate_menus.values()))

조합의 길이 보다, order의 길이가 크거나 같으면, length의 길이를 가지는 조합을 리스트 order로부터 만들 수 있습니다. 조합을 만들어서, 조합의 각 아이템(menu)는 리스트입니다. 딕셔너리의 키로 사용하기 위해서, tuple로 변환하구요, 해당 함께 주문된 메뉴의 횟수에 +1을 합니다.

딕셔너리 candidate_menus에 들어있는 함께 주문된 메뉴들 중에서 가장 많이 주문된 값을 max()함수를 사용해서 찾고, mx에 저장합니다.

 

if mx <= 1:     continue

변수 mx가 1보다 작거나 같다면, 함께 주문된 메뉴중에서 2번 이상 중복해서 주문된 메뉴가 없다는 뜻 이기 때문에, 답에 포함할 수 있는 함께 주문된 메뉴가 없습니다. continue하여 다음 조합의 길이로 이동합니다.

 

변수 mx의 값이 1보다 크다면,

for key in candidate_menus:     if candidate_menus[key] == mx:         answer.append(''.join(list(key)))

딕셔너리 candidate_menus에 포함된어 있는 모든 함께 주문된 메뉴들 중에서, 주문된 횟수가 mx와 같인 메뉴들을 답(리스트 answer)에 추가합니다.

 

answer.sort() return answer

마지막으로, 함께 주문된 메뉴들이 알파벳 순서가 되도록 sort() 하고, 리스트 answer를 리턴합니다.

 

궁금한 문제, 내용은 댓글, 이메일(coding.data.pul@gmail.com)로 보내주세요.

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul

 

전체 코드는 아래에 있습니다.

from typing import List from itertools import combinations from collections import defaultdict def solution(orders: List[str], course: List[int]):     orders = [list(order) for order in orders]     for order in orders:         order.sort()     answer = []     for length in course:         candidate_menus = defaultdict(int)         mx = 0         for order in orders:             if length <= len(order):                 for menu in list(combinations(order, length)):                     candidate_menus[tuple(menu)] += 1                 mx = max(list(candidate_menus.values()))         if mx <= 1:             continue         for key in candidate_menus:             if candidate_menus[key] == mx:                 answer.append(''.join(list(key)))     answer.sort()     return answer