문제
https://programmers.co.kr/learn/courses/30/lessons/72411
코딩테스트 연습 - 메뉴 리뉴얼
레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서
programmers.co.kr
각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
[제한사항]
- orders 배열의 크기는 2 이상 20 이하입니다.
- orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열입니다.
- 각 문자열은 알파벳 대문자로만 이루어져 있습니다.
- 각 문자열에는 같은 알파벳이 중복해서 들어있지 않습니다.
- course 배열의 크기는 1 이상 10 이하입니다.
- course 배열의 각 원소는 2 이상 10 이하인 자연수가 오름차순으로 정렬되어 있습니다.
- course 배열에는 같은 값이 중복해서 들어있지 않습니다.
- 정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 return 해주세요.
- 배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 합니다.
- 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다.
- orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어집니다.
풀이 코드
from itertools import combinations
def solution(orders, course):
answer = []
for c in course:
temp = set()
menu_dic = {}
for order in orders:
order_lst = sorted(list(order))
for i in combinations(order_lst, c):
menu = "".join(i)
if menu in menu_dic.keys():
temp.add(menu)
menu_dic[menu] += 1
else:
menu_dic[menu] = 1
if menu_dic:
max_value = max(menu_dic.values())
if max_value >= 2:
for key in temp:
if menu_dic[key] == max_value:
answer.append(key)
answer = sorted(answer)
return answer
풀이 과정
from itertools import combinations
def solution(orders, course):
answer = []
for c in course:
temp = set()
menu_dic = {}
for order in orders:
order_lst = sorted(list(order))
for i in combinations(order_lst, c):
menu = "".join(i)
if menu in menu_dic.keys():
temp.add(menu)
menu_dic[menu] += 1
else:
menu_dic[menu] = 11. Course별로 max값을 찾아주기 위해 첫번째 반복문을 course로 하였다 ( 처음에 코스가 아닌 orders를 가장 바깥 반복문으로 둬서 조금 헤맸다.
2. 중복을 제거하기 위해 temp라는 임시 set()형식의 저장소를 만들어 주고, 조합 된 코스의 언급을 쉽게 카운트 하기 위해 menu_dic을 선언해줬다. 이 두개의 저장소는 코스의 길이가 바뀔 때 마다 초기화된다.
3. ['A','B']와 ['B', 'A']를 같게 하기 위해 주문서를 하나씩 꺼내 문자열을 문자 단위로 쪼갠 후 정렬한다.
4. 코스에서 가능한 조합을 만들어 하나씩 꺼낸 후 menu_dic에 조합 개수를 count한다.
5. 모든 주문을 돌면서 만들 수 있는 조합의 수를 다 count 한다.
if menu_dic:
max_value = max(menu_dic.values())
if max_value >= 2:
for key in temp:
if menu_dic[key] == max_value:
answer.append(key)
answer = sorted(answer)
return answer
6. 만약 생성 된 조합이 있으면, 그 조합이 언급 된 횟수 중 가장 큰 값을 max_value에 담는다.
7. 이후 max_value가 2 이상이면 아래의 for문을 돌면서 max_value와 같은 값을 가진 key를 answer에다 append한다.
8. 모든 코스를 돌면서 2~7을 반복하고, 모든 for문을 빠져나가면 오름차순으로 정렬한 후 답을 리턴한다.
import collections
import itertools
def solution(orders, course):
result = []
for course_size in course:
order_combinations = []
for order in orders:
order_combinations += itertools.combinations(sorted(order), course_size)
most_ordered = collections.Counter(order_combinations).most_common()
result += [ k for k, v in most_ordered if v > 1 and v == most_ordered[0][1] ]
return [ ''.join(v) for v in sorted(result) ]이건 다른 분의 풀이인데, collections의 Counter함수를 사용했다.
Counter함수는 어떤 단어 및 문자열이 있으면, 거기에 있는 알파벳들의 수를 자동으로 counting 해주는 함수이다.
Counter의 most_common() 메서드는 count가 많은 순 대로 정렬된 배열을 리턴 해주는 메서드이다.
해서 이 풀이는 오름차순으로 정렬한 모든 조합들을 order_combination에 넣은 후 Counter로 집계를 해준다. 그 다음 집계 count가 1 초과이고, 가장 많이 집게 된 것과 같은 값을 갖고 있는 k들을 result에 넣는다. 이를 코스별로 반복한다.