★메뉴 리뉴얼★ (100/100)
★ 다시 풀어봐야할 문제 ★ ( 풀긴 풀었는데 코드가 엄청 지저분함 → Counter 활용하거나 Dict 특징 활용, filter 활용해서 코드 최적화 해보기 )
예전에 풀었던 문제 코드 (예전에 풀었을때도 100/100 이었음 → 그런데 예전에 짰던 코드가 더 깔끔 ㅠㅠ → 결국 짤때마다 코드가 다르게 짜인다는 소리)
'''
아
combination 을 활용해서 각 메뉴 갯수당 가능한 모든 조합의 수를 list에 저장
counter 함수를 활용하여 해당 리스트에 각 메뉴가 몇번 주문되었는지 확인
counter 를 순회하면서 각 course 갯수에 해당하는 최대주문 음식을 dict에 저장
시
자
암
백시투이그
'''
from itertools import combinations
from collections import Counter
def solution(orders, course):
answer = []
o_list = []
ordered = []
for order in orders:
for c in course:
o_list += list(combinations(sorted(order),c))
#print(Counter(ordered).items())
o_dict = {k: [2] for k in course}
for k,v in Counter([''.join(x) for x in o_list]).items():
if v > o_dict[len(k)][0]:
o_dict[len(k)] = [v,k]
elif v == o_dict[len(k)][0]:
o_dict[len(k)].append(k)
print(o_dict)
for c in course:
for x in o_dict[c][1:]:
answer.append(x)
return sorted(answer)접근 방법 [필수 작성]
제한 사항 확인
[제한사항]
- orders 배열의 크기는 2 이상 20 이하입니다.
- orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열입니다.
- 각 문자열은 알파벳 대문자로만 이루어져 있습니다.
- 각 문자열에는 같은 알파벳이 중복해서 들어있지 않습니다.
- course 배열의 크기는 1 이상 10 이하입니다.
- course 배열의 각 원소는 2 이상 10 이하인 자연수가
오름차순으로 정렬되어 있습니다. - course 배열에는 같은 값이 중복해서 들어있지 않습니다.
- course 배열의 각 원소는 2 이상 10 이하인 자연수가
- 정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로
오름차순정렬해서 return 해주세요.- 배열의 각 원소에 저장된 문자열 또한 알파벳
오름차순으로 정렬되어야 합니다. - 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다.
- orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어집니다.
- 배열의 각 원소에 저장된 문자열 또한 알파벳
중요조건
- 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다. → 1번 불린것은 후보군에서 제외된다.
- 단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다.
아이디어
각각 서로 불렸을때마다 각 메뉴의 dict 정보를 갱신하는 방식
AC 에 대해서 A가 C와 같이 불렸다는 정보가 있으려면 dict 의 key 가 AC 의 형태로 저장되어야 함.
즉, 어떤 단품메뉴주문조합 ABC 에 대해서 나올 수 있는 모든 경우의 수를 생각하여
각 dict key 에 1씩 더해주는 방식
ABC
AB = 4, CDE = 3, BCFG = 2, ACDE = 2, 1 1 1
itertools 안 쓰고 해보기
시간복잡도
가장 긴 경우에 대해서 조합의 경우가 몇개가 생기는지 파악
orders = 20 / orders 각 원소길이 = 10 / course = 10 / 오름차순 정렬
한 order 에 대해 나올 수 있는 조합의 수 10C10+10C9+ . . . 10C2
오더는 총 20개 20*(10C10+10C9+ . . . 10C2)
course 에 맞는 value 값 탐색 비용 (10C10+10C9+ . . . 10C2)*10
현재까지 총 30(10C10+10C9+ . . . 10C2) → 최악의 경우 30(10*10C5) → 75600 → ?? 생각보다 얼마 안된다.
맨 처음 리스트를 정렬 후에 작업 시작 → 정렬 시간복잡도 nlogn → 모든 오더의 모든 메뉴에 대해서 정렬 → n = 2010 → 200log(200) → ~200*8 → 1600
예상 전체 연산 수 → 75600 + 1600 → 완탐 가능
자료구조
def combinations() → 각 오더에 대해 나올 수 있는 메뉴조합의 경우의 수 리스트를 리턴해주는 함수
코드 구현 [필수 작성]
#7시10분 시작 ->
def solution(orders, course):
answer = []
sorted_orders = []
combo_list = []
combo_dict = {}
#모든 주문 오름차순으로 정렬
for order in orders:
sorted_orders.append(sorted(order))
# print(sorted_orders)
# print("\n")
def combinations(order,start,tmp_list):
nonlocal combo_list
if len(tmp_list) in course: #course 에 있는 요리갯수의 경우만 생성
combo_list.append(tmp_list[:])
for i in range(start,len(order)):
tmp_list.append(order[i])
combinations(order,i+1,tmp_list)
tmp_list.pop()
#combo_list 생성: 2개 이상 메뉴 조합의 모든 가능한 경우의 수 생성
for order in sorted_orders:
combinations(order,0,[])
#print(combo_list)
for combo in combo_list:
combo_name = "".join(combo)
combo_dict.setdefault(combo_name,[0,len(combo_name)])
combo_dict[combo_name][0] += 1
#combo_dict.sort(*, key=combo_dict.value, reverse=False)
sorted_combo_dict = sorted(combo_dict.items(), key=lambda x:x[1][0], reverse=True)
print(sorted_combo_dict)
for menu_size in course:
max_count_about_menu_size = -1 #이 값은 최대 20이 될 수가 있음
for key,value in sorted_combo_dict:
if value[1] == menu_size:
max_count_about_menu_size = max(max_count_about_menu_size,value[0])
if value[1] == menu_size and value[0] == max_count_about_menu_size and value[0] >= 2:
answer.append(key)
return sorted(answer)sorted_combo_dict 의 구조
type: list
ex: [ (string:Menu Combo, [int:Count,int:Menu Size] ) , … ]
배우게 된 점 [ 필수 X ]
문제 똑바로 읽고 최적화할 수 있는 방향 생각하기
→ 필요없는 최대조합수 만들필요 없었음. course 내에 있는 메뉴갯수 조합에 대해서만 찾으면 됨.
setdefault 딕셔너리 안에 없으면 0 으로 초기화 하는 딕셔너리 함수를 활용하면
굳이 if 문으로 귀찮게 없을 경우에는 초기화하는 코드 짤 필요 없음
combo_dict.setdefault(combo_name,[0,len(combo_name)])
combo_dict[combo_name][0] += 1(key,value) 쌍을 iterator 로 받고 싶다면, dict.items() 활용!
for key,value in combo_dict.items():문제 또 제대로 안 읽었다.
- “ 가장 많이 함께 주문된 단품메뉴 조합에 따라”
filter(function, iterable) 함수를 활용해서 최대값을 같은 메뉴조합만 골라낼 수 있다! filter 함수 활용하자
질문 [ 필수 X ]
Q1
기업별로 라이브러리 활용을 막는 코딩테스트도 있기에 외부 라이브러리 함수를 활용하는데 거부감을 느끼게 된다. 과연 내가 라이브러리를 활용할 수 없을때, 그 문제를 풀 수 있을것인가? 하는 의구심이 든다. 외부 라이브러리 함수를 거부감 없이 써도 되는가?
→ 라이브러리 함수를 제한하는 코테는 비중이 굉장히 적기도 하고, 특히나 python 은 더더욱 그렇다. 그래서 외부 라이브러리 함수 활용에 거부감을 느낄 필요는 없다. 하지만, 함수 동작 코드를 직접 찾아보고 함수 동작 방식을 이해하고 공부해놓는다면, 실제로 시험장에서 사용이 제한된다고 하더라도, 그 작동 방식을 이해하고 있다면, 직접 구현해서 활용하는데 어려움은 없을 것이다.
Q2
이번에 문제를 다시 풀어보면서 처음에 문제조건을 이해하는데 문제가 너무 길다보니 완벽하게 이해하지 못하고 우선 풀기 시작하다보니 문제 풀이가 굉장히 더러워졌습니다. 또, 문제를 다 풀고, 과거에 제가 어떻게 풀었었는지 제 코드를 봤는데 dict 구성을 굉장히 깔끔하게 해서 제 코드에 저 스스로 감탄했습니다. 문제는 매번 풀때마다 저조차도 코드 스타일이 달라지는데 어떻게 하면 코딩테스트에서 일관되게 좋은 코드를 짤 수 있을지, 어떻게 하면 문제를 깔끔하게 이해하고 정리할 수 있을지 코치님의 팁이 있다면 들어보고 싶습니다. 질문이 굉장히 막연하기에 답변하기 힘드시다면 답변을 스킵하셔도 괜찮습니다.
피드백 [ 코치 작성 ]
일관된 코드를 작성하는 것과 문제를 깔끔하게 이해하는 것, 이 모든 것들은 문제를 많이 풀어보는 방법밖에는 없습니다. 수험생들이 수능을 공부할 때 흔히 말하는 양치기를 하는 것과 동일하죠. 문제는 모두 정해진 유형이 있으며 그 유형의 틀에서 크게 벗어나지 않습니다. 그렇기에 많은 문제를 풀어본다면 새로 접하는 문제라고 하더라도 기존에 풀어본 문제의 유형일 가능성이 크며 문제의 유형을 알 경우 문제를 이해하는 것에 큰 도움을 줍니다.
