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

문제 설명

제한사항 및 입출력

풀이

역시 카카오답게 문제가 쉽지않다. 정리해보자면 손님이 단품으로 주문한 메뉴들과 만들어야하는 코스요리에 포함되어야하는 단품 요리 수가 주어지고, 만들어야하는 코스 요리의 제약조건은 다음과 같다.

1. 2개 이상의 메뉴로 이루어져야함.

2. 2명 이상의 손님이 주문한 메뉴여야함

3. 각 코스요리 별로 가장 많이 주문된 메뉴 구성을 사전순으로 출력 (만약 같다면 모두 출력)

 

이를 위해 역시 가장 먼저 생각난 방법은 조합이다. orders와 course의 배열 크기가 작아 모든 조합을 찾을 수 있다는 생각이 들었다. 각 주문들을 순회하며 주어진 코스요리의 개수만큼 모든 조합을 만들고, 해시맵으로 관리하면서 이미 존재한다면 나온 수를 올려주고 없다면 추가해주는 방식으로 풀이하였다.

내 코드

from collections import Counter
from itertools import combinations
  
def solution(orders, course):
    # 길이 i 코스요리의 종류와 빈도
    counts = {i: Counter() for i in course}

    # 개수 세기 (길이에 따른 모든 조합)
    for i in orders:        
        for j in course:
            if len(i) >= j:
                for comb in combinations(i, j):
                    counts[j][''.join(sorted(comb))] += 1   # WX, XW 처럼 같은 키가 분리되는 경우

    ans = []
    for i in course:
        if not counts[i]: continue
        
        # 길이 i의 코스요리의 종류에서 2명 이상이 시킨 조합들 중 빈도가 최댓값 조합만 ans에 추가
        max_cnt = max(counts[i].values())
        if max_cnt >= 2:
            ans += [k for k, v in counts[i].items() if v == max_cnt]
        
    return sorted(ans)

처음엔 counts 해시맵에 키를 정렬하지 않고 넣어주었더니 WX, XW와 같은 경우를 잡지 못해 올바른 해를 도출해주지 못했다. 추가적으로 키를 넣을 때 정렬해주어 해결해주었다. 지금 생각해보니 그냥 order를 순회할 때 i를 정렬해주어도 되었는데 왜 이렇게 했을까... 

이렇게 만들어준 메뉴 길이 별 코스요리의 모든 조합들을 순회하며 가장 빈도가 많은 조합만 ans에 추가해주어 풀이했다.