メニュー更新問題リンク

問題の説明

お客様1人につきご注文の際に一番多い単品メニューをセットメニューとしてご用意しております.
ただし、セットメニューは少なくとも2種類以上の単品メニューからなり、少なくとも2名以上のお客様から注文した単品メニューの組み合わせについては、セットメニューの候補リストにのみ含まれる.
各お客様が注文した単品メニューが文字列形式で含まれる並び順で、作成するコースを構成する単品メニューが個数の並び順をパラメータとすると、新しく追加されたコースのメニュー構成が得られます.
(お客様1人につき2つ以上の単品メニューを注文しなければなりません.各単品メニューはアルファベットA~Zで表示されます)

例

6名様からご注文いただいた単品メニューの組み合わせは以下の通りです.
お客様番号注文の単品メニューセット1番お客様A、B、C、F、G 2番お客様A、C 3番お客様C、D、E 4番お客様A、C、D、E 5番お客様B、C、F、G 6番お客様A、C、D、E、H
最も多く一緒に注文する単品メニューの組み合わせにより、「skapi」が作成するコースメニュー構成候補は以下の通り.
コースメニュー構成説明料理2コースA、C 1番、2番、4番、6番のお客様は全部で4番を注文しました.3品の料理C、D、E 3番、4番、6番のお客様は全部で3品の料理を注文しました.4品B、C、F、G 1、5番のお客様は全部で2品注文しました.4品A C D E 4番6番のお客様は全部で2番をご予約いただいております

に答える

初めての試み

アイデア

注文したすべてのメニューを組み合わせます。

すべての注文した単品メニューを使用リストに入れ、これらのメニューで組み合わせを構成します.

結果

しかしタイムアウトが発生した.orders=["AB","CD"]なら[A,B]と[C,D]の組み合わせを見つけるだけでいいのですが、今のようにすれば[A,C],[A,D],[B,D],[C,D],[C,D]の組み合わせが見つかり照合されます.注文の価格はますます多様化し、長ければ長いほど長くなります.

コード#コード#

from collections import defaultdict


def solution(orders, course):
    def get_order_count(new_course): # 각 코스별로 몇 번 주문되었는지 count
        count = 0
        for order in orders:
            if new_course & set(order) == new_course:
                count += 1
        return count
        
    def make_course(target_count, index, count, selected):
        if count == target_count: # 코스 조합을 다 만들었다
            order_count = get_order_count(set(selected)) # 만든 코스가 주문된 횟수를 구한다
            
            if order_count < 2: # 주문 횟수가 2보다 작다면 저장할 필요 없다
                return
            
            courses_by_count[order_count].append(''.join(selected))
            return
        
        if index == len(used):
            return
        
        selected[count] = used[index]
        make_course(target_count, index + 1, count + 1, selected)
        make_course(target_count, index + 1, count, selected)


    used = set() # 주문된 단품메뉴
    for order in orders:
        used = used | set(order)
    used = list(used)
    used.sort()
        
    result = []
    for target_count in course:
        courses_by_count = defaultdict(list) # 주문횟수 별 코스들
        
        selected = [''] * target_count # 코스를 만들기 위해 사용하는 배열
        make_course(target_count, 0, 0, selected)
        
        if courses_by_count:
            max_count = max(courses_by_count.keys())
            result.extend(courses_by_count[max_count])
    
    result.sort()
    return result

2回目の試み

アイデア

お客様が注文したメニューごとに組み合わせます。

結果

コード#コード#

from collections import defaultdict


def solution(orders, course):
    def get_order_count(new_course): # 각 코스별로 몇 번 주문되었는지 count
        count = 0
        for order in orders:
            if new_course & set(order) == new_course:
                count += 1
        return count
        
    def make_course(target_count, index, count, selected):
        if count == target_count: # 코스 조합을 다 만들었다
            order_count = get_order_count(set(selected)) # 만든 코스가 주문된 횟수를 구한다
            
            if order_count < 2: # 주문 횟수가 2보다 작다면 저장할 필요 없다
                return
            
            courses[order_count].add(''.join(selected))
            return
        
        if index == len(order):
            return
        
        selected[count] = order_arr[index]
        make_course(target_count, index + 1, count + 1, selected)
        make_course(target_count, index + 1, count, selected)

        
    result = set()
    for target_count in course: # 만들어야할 코스의 단품 개수
        courses = defaultdict(set) # 주문횟수 별 코스들
        for order in orders: # 주문별로 반복
            order_arr = sorted(list(order)) # 문자열을 분리해 정렬한 리스트

            selected = [''] * target_count # 코스 조합을 만들기 위해 사용하는 배열
            make_course(target_count, 0, 0, selected)

        if courses:
            max_count = max(courses.keys())
            result = result | courses[max_count]
    
    return sorted(list(result))