메뉴 리뉴얼[Python]

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

문제 설명

• 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.
• 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 “스카피”는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.

• 단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.

• 예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면,
• (각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)

• 가장 많이 함께 주문된 단품메뉴 조합에 따라 “스카피”가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.

문제

• 각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, “스카피”가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, “스카피”가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

• orders 배열의 크기는 2 이상 20 이하입니다.
• orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열입니다.
• 각 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 각 문자열에는 같은 알파벳이 중복해서 들어있지 않습니다.
• course 배열의 크기는 1 이상 10 이하입니다.
• course 배열의 각 원소는 2 이상 10 이하인 자연수가 오름차순으로 정렬되어 있습니다.
• course 배열에는 같은 값이 중복해서 들어있지 않습니다.
• 정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 return 해주세요.
• 배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 합니다.
• 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다.
• orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어집니다.

문제풀이

• count_order 함수는 python의 내장함수인 itertools의 combinations를 사용해서 orders에서 주어진 숫자의 경우의 수를 구한다 (중복 허용하지 않음)
  • 다만 위처럼 하면 XY와 YX는 다른 문자로 인식하지만 문제에선 XY와 YX를 같게 보기 떄문에, orders를 sort 해준다.
  • 이후 map과 list를 사용하여 join을 해서 (X, Y), (W, Y)로 되어있는 값을 [XY, WY] 형태로 변환한다.
• soultion은 count_order로 구한 경우의 수를 python 내장함수인 Counter로 갯수를 세서 answer에 저장한다.
  • 가장 많은 갯수를 가진 경우의 수를 answer에 저장한다.
  • 만약 경우의 수가 1개도 없거나, 모든 조합이 1개일 경우에는 셋트메뉴 구성이 안되므로 넘긴다.
  • 위의 경우가 아니라면 answer에 가장 많은 조합을 answer에 저장한다.
  • 마지막으로 answer를 알파벳순으로 정렬하고 return 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import itertools
from collections import Counter

def count_order(orders, n):
    answer = []
    for order in orders:
        order = sorted(order)
        answer.extend(list(map(''.join, itertools.combinations(order, n))))
    return answer

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

    for n in course:
        results = []
        results.extend(count_order(orders, n))

        cnt = Counter(results)
        
        if len(cnt) !=0 and max(cnt.values())>1:
            answer += [key for key, value in cnt.items() if value == max(cnt.values())]
    return sorted(answer)

1
2
3

orders = ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]
course = [2,3,4]
solution(orders, course)

1

['AC', 'ACDE', 'BCFG', 'CDE']

1
2
3

orders = ["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"]
course = [2,3,5]
solution(orders, course)

1

['ACD', 'AD', 'ADE', 'CD', 'XYZ']

1
2
3

orders = ["XYZ", "XWY", "WXA"]
course = [2,3,4]
solution(orders, course)

1

['WX', 'XY']

1
2
3

orders = ["ABCD", "ABCD", "ABCD"]
course = [2,3,4]
solution(orders, course)

1

['AB', 'ABC', 'ABCD', 'ABD', 'AC', 'ACD', 'AD', 'BC', 'BCD', 'BD', 'CD']

1
2
3

orders = ["ABCDE", "AB", "CDAB", "ABDE", "XABYZ", "ABXYZ", "ABCD", "ABCDE", "ABCDE", "ABCDE", "AB", "AB", "AB", "AB", "AB", "AB", "AB", "AB", "AB", "AB"]
course = [2]
solution(orders, course)

1

['AB']

1
2
3

orders = ["ABCD", "ABCD", "ABCD"]
course = [2,3,4]
solution(orders, course)

1

['AB', 'ABC', 'ABCD', 'ABD', 'AC', 'ACD', 'AD', 'BC', 'BCD', 'BD', 'CD']