[프로그래머스] Lv2. 메뉴 리뉴얼 (2021 카카오 공채)

🔗

풀이

가장 많이
함께 주문한

모든 메뉴들의 조합들 중에서 2번 이상 주문됐으면서 조합의 길이별로 가장 많이 주문된 조합들을 찾아야 한다.

'AB'라는 메뉴가 3번, 'CD'라는 메뉴가 4번 주문됐다면 길이가 2인 조합 중에서는 'CD'가 반환되어야 한다.

만약 횟수가 같다면 둘 다 반환한다. 이 문제는 문제 해석이 너무 어려웠다.

🫠 내 풀이

각 주문별로 가능한 모든 조합을 만든 다음에 menu 딕셔너리에 저장했다. 그런 다음 딕셔너리를 돌면서 가장 최대값 또는 최대값과 같은 값을 갖는 키 값들을 찾았다. (1보다 크면서)

def solution(orders, course):
    menu = {}

    for order in orders:
        for k in range(2, len(order)+1):
            for comb in combinations(order, k):
                key = ''.join(sorted(comb))
                menu[key] = menu.get(key, 0)+1

    combs = {x: [['', -1]] for x in course}
    for key, value in menu.items():
        l = len(key)
        if l in course:
            if combs[l][0][1] < value:
                combs[l] = [[key, value]]
            elif combs[l][0][1] == value:
                combs[l].append([key, value])

    answer = []
    for comb in combs.values():
        answer.extend([cmb[0] for cmb in comb if cmb[1] >= 2])

    answer.sort()
    return answer

from itertools import combinations

🤩 효율적인 풀이

구하려고 하는 건 course에 있는 조합의 길이만큼만 구하면 된다. [2, 3, 4]라면 2, 3, 4의 길이를 갖는 조합만 구하면 되기 때문에 굳이 모든 주문들에 대한 모든 조합을 다 구할 필요가 없었다.

그리고 각 길이에 대해서 1보다 큰 최빈값들을 모두 구해서 result 배열에 문자열로 변경해서 추가한다. 배열은 사전순으로 출력하라고 했으므로 정렬한 후 값을 반환한다.

def solution(orders, course):
    orders = [sorted(o) for o in orders]
    
    result = []
    for size in course:
        menu_comb = []
        for order in orders:
            menu_comb += combinations(order, size)
            
        most_ordered = Counter(menu_comb).most_common() 
        result.extend([''.join(menu) for menu, cnt in most_ordered if cnt > 1 and cnt == most_ordered[0][1]])
    
    result.sort()
    return result
            
from itertools import combinations
from collections import Counter

팁

Counter의 most_common()

Counter를 통해 생성된 딕셔너리에서 키 값의 내림차순으로 구할 수 있는 메서드이다. 최빈값을 구할 때 자주 사용되며 most_common(1) 과 같은 형식으로 사용하게 되면 괄호 안의 숫자만큼의 개수만 찾을 수 있다. 가장 큰 3개의 데이터와 같은 값을 구할 때 유용하다.