[프로그래머스] 2. 메뉴 리뉴얼 (2021 Kakao Blind Recruitment)

Problem Link : https://programmers.co.kr/learn/courses/30/lessons/72411
Language : Python 3

문제 정의

문제에서는 주어진 변수는 다음과 같습니다.

• 손님들이 주문한 단품 메뉴들의 배열 orders
• 요리사가 추가하고자 하는 코스요리를 구성하는 단품 메뉴 개수의 배열 course

문제에서 요구하는 바는, 요리사가 새로 추가하게 될 코스요리의 메뉴 구성의 배열을 리턴하면 됩니다. 추가적으로 조건은 다음과 같습니다.

• 코스요리 메뉴는 손님들이 가장 많이 함께 주문한 단품메뉴 조합으로 구성합니다.
  • 가장 많이 함께 주문한 단품메뉴 조합이 여러 개라면 모두 포함시킵니다.
  • 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합만 포함시킵니다.
• 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다.
• 코스요리 배열을 '오름차순 정렬'합니다.

예를 들어, 다음의 간단한 예제를 생각해봅시다.

 

orders	course	result
["ABC", "ABD", "AB", "AC", "ACD"]	[2]	["AB", "AC"]

 

이 문제의 조건은

1. 단품 메뉴 개수 배열(course)에 따르면, 코스요리를 구성하는 단품 메뉴가 2개입니다.
2. 단품 메뉴 주문 기록(orders)에 따르면, 주문된 단품 메뉴 조합은 다음과 같습니다.
   1. "AB" 조합을 3번 주문
   2. "AC" 조합을 3번 주문
   3. "AD" 조합을 2번 주문
   4. "BC", "BD", "CD" 조합을 1번 주문

결과(result)는 ["AB", "AC"]가 됩니다.

 

문제 풀이

큰 목표는 단품 메뉴 주문 기록(list of strings)에서 course의 개수 만큼의 메뉴(character) 수를 가지는 문자열을 뽑는 것입니다.

일반적인 조합 문제와 한 가지 다른 점은, 조합 문자열의 출현 빈도를 기록해야 한다는 점입니다. 또한, 빈도가 가장 높은 (다수의) 문자열을 알파벳 순으로 오름차순 정렬하여 리턴해야 합니다.

 

combination 함수는 order 문자열로부터 c개의 단품 메뉴(character) 개수를 갖는 새로운 단품 메뉴 조합 comb 문자열를 만들어서, comb를 key로 출현 빈도를 value로 하는 dictionary count에 저장할 것입니다. (최대 출현 빈도 순으로 정렬할 것이므로 priority queue에 저장하는 것이 좋을 수도 있습니다)

 

직접 combination 함수를 짤 수도 있지만 (완성된 코드 1), 파이썬의 itertools.combinations와 collections.Counter를 이용하여 간편하게 코드를 구현할 수도 있습니다 (완성된 코드 2).

 

완성된 코드 1. 조합 함수 작성

from operator import itemgetter

def combination(k, c, comb, order, count):
    """
    k: current index of single menu
    c: target num of single menu
    comb: single menu combination
    order: ordered menu
    count: count of ordered menu
    """
    if len(comb) == c:
        count[comb] = count[comb]+1 if comb in count else 1
        return

    for i in range(k+1, len(order)):
        comb += order[i]
        combination(i, c, comb, order, count)
        comb = comb[:-1]

    return 


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

    for c in course:
        count = dict()  # menu count

        for order in orders:
            order = ''.join(sorted(order))
            combination(-1, c, '', order, count)

        count = sorted(tuple(count.items()), key=itemgetter(1), reverse=True)
        answer += [i[0] for i in count if i[1] == count[0][1] and i[1] > 1]

    answer = sorted(answer)

    return answer

완성된 코드 2. itertools.combinations와 collections.Counter 사용

from itertools import combinations
from collections import Counter

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

    for c in course:
        comb_list = list()

        for order in orders:
            comb_list += combinations(sorted(order), c)

        count = Counter(comb_list).most_common()        
        answer += [l[0] for l in count if (l[1] == count[0][1] and l[1] > 1)]

    answer = [''.join(a) for a in sorted(answer)]

    return answer

참고한 코드

• 조합과 순열 알고리즘, 파이썬으로 구현하기
• [Python 알고리즘] python으로 순열과 조합 직접 구현하기