프로그래머스 - 메뉴 리뉴얼

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/72411

문제 요약

1. 음식코스를 만들기 위해서 사람들이 주문한 메뉴와 원하는 코스 구성요소 수가 주어진다.
2. 사람들이 가장 자주 시킨 조합으로 코스를 짜는 알고리즘을 구현
3. 단, 적어도 2명의 사람이 시킨 조합으로만 짤 것

풀이요약

주어진 범위가 매우 작다
1. 주문한 메뉴를 주어진 코스의 구성요소 수만큼 조합을 뽑아낸다.
2. 조합을 key값으로 가지는 dictionary에 +1을 해준다
3. 조합의 길이 즉, 코소 구성요소 수를 key값으로 가지는 dictionary에 2의 최댓값을 갱신한다.

코드

from collections import defaultdict
from itertools import combinations

def solution(orders, course):
	# 조합이 몇 번 나왔는지 저장할 배열
    cnt = defaultdict(int)
    # 각 구성요소 수의 최댓값을 갱신할 배열
    max_v = defaultdict(int)
    
    
    for order in orders:
    	# 사전순이어야 해서 정렬해준다.
        order = "".join(sorted(order))
        # 구성요소 수를 for문으로 돌린다.
        for i in course:
        	# 구성요소 수만큼 조합을 뽑는다.
            for j in combinations(order, i):
                j = "".join(sorted(j))
                cnt[j] += 1
                # 만약 구성요소 수의 최댓값이 갱신될 수 있다면 갱신
                if max_v[i] < cnt[j]:
                    max_v[i] = cnt[j]

    answer = []
    for j in cnt.keys():
        temp = len(j)
        # 만약 해당 조합이 1명 밖에 시키지 않았다면 예외처리 해준다.
        if max_v[temp] == cnt[j] and max_v[temp] != 1:
            answer.append(j)

    answer.sort()
    return answer

후기

1. 다른 사람 코드를 보니 조합을 다 뽑고 Counter를 사용했던데 코드가 훨씬 짧아졌다
2. orders 배열의 최대 길이가 20, orders안에 시킨 메뉴 수가 최대 10가지라서 가능했던 풀이