[Python] 프로그래머스 2021 KAKAO BLIND RECRUITMENT : 메뉴 리뉴얼

프로그래머스 2021 KAKAO BLIND RECRUITMENT : 메뉴 리뉴얼

문제 풀이

orders에서 course에 따른 조합을 만들어 count를 하고, max count에 해당하는 조합들을 answer에 append 하면 된다.

나는 dfs 방식과 defaultdict 함수를 사용하여 단품메뉴 조합을 구하고, 조합의 count를 구했다.

답

from collections import defaultdict
# dfs(단품메뉴, 단품메뉴 갯수, 단품메뉴 인덱스, 단품메뉴 조합 배열, 단품메뉴 조합 count)
def dfs(order, num, idx, combinations, dint):
	# 단품메뉴 조합을 count 한다.
    if len(combinations) == num: 
        tmp = ''
        for com in combinations:
            tmp += com
        dint[tmp] += 1
        return
    # 인덱스가 넘어서 return
    elif idx >= len(order):
        return
    # 단품메뉴 조합을 만든다.
    else:
        for i in range(idx, len(order)):
            combinations.append(order[i])
            dfs(order, num, i+1, combinations, dint)
            combinations.pop()

def solution(orders, course):
    dint = defaultdict(int)
    answer = []
    combinations = []
    # course 별로 order들을 조합한다.
    for num in course:
        for order in orders:
            dfs(sorted(order), num, 0, combinations, dint)
        # 단품메뉴 조합이 존재한다면, max 값 찾기
        if dint:
                max_value = max(dint.values()
        # max_value에 해당하는 단품메뉴 조합들을 asnwer에 append 
        if max_value > 1: # 2개 이상 존재해야 하기 때문에 2 이상
            for key,val in dint.items():
                if val == max_value:
                    answer.append(key)
        dint = defaultdict(int)
    answer.sort() # 정렬하여 return
    return answer