[프로그래머스] 메뉴 리뉴얼

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

코딩테스트 연습 - 메뉴 리뉴얼

 

 

<문제 설명>

코스요리를 만들려고함.
각 손님들이 가장 많이 함께 주문한 단품메뉴 조합을 코스요리 메뉴로 구성.
최소 2가지 이상의 단품메뉴여야 하고, 최소 2명 이상의 손님이 주문한 메뉴 조합만 후보에 포함.

 

course라는 매개변수에 담긴 수만큼의 음식을 포함하는 코스요리를 만들 것임.

각 수만큼 가장 많이 사람들이 시킨 음식 조합을 찾아야함.

이때 같은 음식 수에서 사람들이 시킨 횟수가 같으면 모두 리턴

 

 

 

<문제 이해>

일단 매개변수 course로 주어진 조합 수에 맞춰 음식의 조합을 구한다.

그리고 얼마의 사람들이 함께 시켰는지 구한다.

조합 수 별로 가장 많이 시킨 음식 조합을 배열에 담아 리턴한다.

 

 

 

<문제 풀이>

음식의 조합을 찾아내기 위해서 dfs를 사용하였고(findCombi()),

그 음식의 조합을 사람들이 얼마나 시켰는지에 대해 구해

조합 수 별 [음식조합, 주문수]로 딕셔너리에 저장했다(check()).

그리고 딕셔너리 속에 있는 조합 수 별로 저장된 배열 데이터를 정렬하고

가장 높은 주문 수를 가진 음식을 정답 배열에 넣고 그 배열을 출력하는 방식을 이용하였다.

음식 조합 주문 수가 겹치는 경우도 고려하여 코드를 작성했다.

orderSet = set()
orderCnt = {}

def solution(orders, course):
    answer = []

    for order in orders:
        findCombi(0, order, '', course)

    for c in course:
        orderCnt[str(c)] = []

    for combi in orderSet:
        check(combi, orders)

    for oc in orderCnt:
        cntList = sorted(orderCnt[oc], key = lambda x : x[1], reverse=True)
        if len(cntList) > 0:
            top = cntList[0][1]
            for cl in cntList:
                if cl[1] == top: answer.append(cl[0])
                else : break

    answer = sorted(answer)

    return answer

def findCombi(index, order, combi, course):
    if index == len(order):
        if len(combi) in course:
            orderSet.add(''.join(sorted(combi)))
        return

    findCombi(index+1, order, combi, course)
    findCombi(index+1, order, combi+order[index], course)


def check(combi, orders):
    global answer, orderCnt

    count = len(orders)

    for order in orders:
        for c in combi:
            if c not in order:
                count -= 1
                break

    if count >= 2 : 
        orderCnt[str(len(combi))].append([combi,count])

    return

 

 

 

<풀이 개선>

다른 사람들이 풀이를 보니 여러 라이브러리를 사용한 것을 알 수 있었고,

내가 위에 썼던 코드들을 아주 짧은 코드로 해결할 수 있는 함수들이 있다는 것을 알았다.

itertools.combinations()은 문자를 c개의 조합으로 된 문자열 리스트를 리턴하는 함수이고,

collections.Counter()은 위에서 만들어진 리스트를 카운터해서 딕셔너리를 리턴하는 함수이다.

마지막으로 most_common()은 위의 딕셔너리를 value 값이 높은 것을 기준으로 내림차순 정렬을 해주는 함수이다.

 

위의 3개의 함수를 이용하여,

주어진 course 속에서 수를 하나씩 꺼내 그 수와 같은 음식 조합을 만들고,

그 조합에서 가장 많이 사람들이 찾은 음식조합을 내림차순으로 정렬해

가장 많이 시킨 음식조합을 찾아내는 코드이다.

import itertools
import collections

def solution(orders, course):
    answer = []
    
    countList = []
    for c in course:
        countList = []
        for order in orders:
            countList += list(itertools.combinations(sorted(order), c))
        countDict = collections.Counter(countList).most_common()

        if len(countDict) > 0:
            maxCnt = countDict[0][1]
            for d in countDict:
                if maxCnt == d[1] and maxCnt >= 2:
                    answer += [''.join(d[0])]
    
    return sorted(answer)

 

 

 

나는 진짜 오래 걸려서 풀었는데

몰랐던 라이브러리 속 함수로 풀면 이렇게 짧고 쉽게 풀 수 있다는 것을 깨달았다,,,,

라이브러리의 중요성,,,,

어렵다 어려워