from collections import defaultdict
from itertools import combinations
# 리스트 평탄화하는 함수
def Flatten(li):
result = []
for item in li :
if type(item) == tuple :
result += Flatten(item)
else :
result += [item]
return result
def solution(orders, course):
answer = []
combi = defaultdict(list)
lists = defaultdict(int)
for order in orders:
order = sorted(order) # 알파벳 미리 정렬
for num in course :
for i in combinations(order, num) :
lists[''.join(i)] += 1
lists = list(lists.items())
for li in lists :
comb = combi[len(li[0])]
if len(comb) == 0: # 아직 아무것도 안 들어온 상태일 때는 그냥 저장
combi[len(li[0])] = li
elif li[1] > comb[1] : # 현재 메뉴 조합의 주문수가 더 많으면 바꿔치기
combi[len(li[0])] = li
elif li[1] == comb[1] : # 주문수 같을 땐 기존 것까지 포함해서 모두 저장
combi[len(li[0])] = (comb[0], li[0]), comb[1]
for key, val in combi.items() :
if val[1] >= 2 :
for v in val :
if type(v) != int :
answer.append(v)
answer = sorted(Flatten(answer))
return answer
자잘한거 때문에 시간 많이 걸린 문ㅈㅔ ㅡ.,ㅡ
암튼하나씩 설명해보겠다
for order in orders:
order = sorted(order) # 알파벳 미리 정렬
for num in course :
for i in combinations(order, num) :
lists[''.join(i)] += 1
lists = list(lists.items())
lists 출력해본 결과인데
이런 식으로 course 에 해당하는 경우의 수가 모두 나오게 하려고
combinations 모듈 사용함
그리고 예를 들어서 "WX" 랑 "XW" 은 동일한 걸로 쳐야 되는데 각각 1번씩 나오길ㄹㅐ,,
그냥 그전에 미리 sorted() 사용해서 정렬해준거
for li in lists :
comb = combi[len(li[0])]
if len(comb) == 0: # 아직 아무것도 안 들어온 상태일 때는 그냥 저장
combi[len(li[0])] = li
elif li[1] > comb[1] : # 현재 메뉴 조합의 주문수가 더 많으면 바꿔치기
combi[len(li[0])] = li
elif li[1] == comb[1] : # 주문수 같을 땐 기존 것까지 포함해서 모두 저장
combi[len(li[0])] = (comb[0], li[0]), comb[1]
combi 도 defaultdict(int) 딕셔너리인데,
{ 메뉴 조합 가지 : (메뉴 조합, 주문된 횟수) }
ex) { 5 : ('ABCDE', 1) } => ABCDE 메뉴조합은 1번 주문되었다는 뜻
주문수가 같을 때는 기존에 저장되어 있던 메뉴조합이랑 같이 묶어서
{ 2 : ( ('AD', 'CD'), 3) } 이런 식으로 나오게끔 했다
for key, val in combi.items() :
if val[1] >= 2 :
for v in val :
if type(v) != int :
answer.append(v)
answer = sorted(Flatten(answer))
코드만 보면 이해 안 가니께,,
combi 딕셔너리에서 Key 랑 Value 출력해봄
주문 횟수가 2회 이상이여야 되니까 val[1] 에 조건 걸어주고,
answer 배열에는 주문 횟수말고 메뉴 조합만 저장해야 하니까
정수 type 인지 아닌지 검사해준거 !!
그리구 마지막에 Flatten 함수 호출해주고 정렬해주면 끝 ~~~
# 리스트 평탄화하는 함수
def Flatten(li):
result = []
for item in li :
if type(item) == tuple :
result += Flatten(item)
else :
result += [item]
return result
아니 이것 때문에 한참을 ...
2차원 리스트 1차원으로 바꾸는 함수인데
리스트 순회하면서 튜플 형태면 Flatten 함수 재귀 호출하면 됨 그럼 진짜 진ㅇ짜 끝 !!!
'알고리즘' 카테고리의 다른 글
[프로그래머스 Lv2 - 2020 KAKAO BLIND RECRUITMENT] 문자열 압축 (Python) (0) | 2022.09.29 |
---|---|
[프로그래머스 Lv2] N-Queen (Python) (1) | 2022.09.22 |
[프로그래머스 Lv2 - 2022 KAKAO BLIND RECRUITMENT] 양궁 대회 (Python) (3) | 2022.09.19 |
[프로그래머스 Lv2 - 2022 KAKAO BLIND RECRUITMENT] k진수에서 소수 개수 구하기 (Python) (0) | 2022.09.16 |
[프로그래머스 Lv2 - 2022 KAKAO BLIND RECRUITMENT] 주차 요금 계산 (Python) (0) | 2022.09.16 |