문제
문제 해설
딕셔너리와 조합을 이용해 푸는 문제입니다.
각 제한사항을 꼼꼼히 확인한 뒤, 조합을 써도 시간이 넉넉할 것 같아 조합을 사용해 풀었습니다.
answer를 리턴할 때 안에 있는 요소들은 정렬된 상태여야 하며, 요소 안의 문자들도 정렬이 된 상태여야 합니다.
일단 orders의 요소들, 요소안의 문자들은 정렬되어 있지 않은 상태입니다. 그러므로 정렬을 해주는데, 딕셔너리에 key-value로 값을 저장할 때 정렬이 되어있지 않은 상태라면 {"CA":1, "AC":1}처럼 같은 조합인데도 불구하고 따로 저장되는 불상사를 방지하기 위함입니다.
다음은 주어진 course만큼 조합해야 합니다. 조합한 뒤 딕셔너리에 저장하는데, 위에서 이미 정렬을 해놓고 조합을 뽑은 것이라, 조합된 결과도 정렬된 상태입니다.
마지막으로 딕셔너리에서 가장 큰 값을 확인하고, 2 이상일 때 가장 큰 값들을 모두 빼면 됩니다.
풀이 코드
from itertools import combinations
def solution(orders, course):
answer = []
for cnt in course:
d = {}
for order in orders:
l = sorted(list(map(str, order)))
# orders를 리스트로 변환, 정렬 후 cnt만큼 조합
for com in combinations(l, cnt):
# 조합된 음식들 딕셔너리에 저장
string = "".join(com)
d.setdefault(string, 0)
d[string] += 1
# 조합을 만들 수 없는 상황 처리
max_val = max(d.values()) if d else 0
# 적어도 두명 이상에게서 나온 요리 조합이어야 함
if max_val >= 2:
for k, v in d.items():
# 최대로 많이 나온 조합을 모두 넣어줌.
if v == max_val:
answer.append(k)
answer.sort()
return answer