2021 KAO BLINDメニュー更新

質問する

問題は次のとおりです.
https://programmers.co.kr/learn/courses/30/lessons/72411
入力

orders:お客様が注文した単品メニューを文字列で並べる

course:追加したいセット数を含む単品メニューの並び

しゅつりょく
新しく追加されたコース料理のメニュー構成を含む文字列配列.

アルファベット順に並べなければならない

方法

最初は交差で解きたいと思っていました.
まず、内部文字列の長さに基づいてOrdersをソートします.
長さの小さいorderから、後ろのorder交差要素を順に
一つの方法を考えて盛り付けながら、重ねたメニューを数えました.
しかし、問題があることに気づき、問題を読み直した.
ordersの要素orderをnと見なし、courseの要素cをrと見なしたらどうですか.
想像してみてくださいnCrnCrn
orders : ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]
order(=forin orders)でrをマージすると
orderのr個の組合せを求めることができる.
結果をdictionaryに入れてcountを行い、ordersでループを行い、終了後にcourseループを行い、すべての組合せ状況を含む数とそのcountを含むdictionaryを求める.
そのコードは以下の通りです.

import itertools

def solution(orders, course):
    answer = []
    # n_C_r
    dic_course = dict()
    while course:
        r = course.pop(0)
        
        for order in orders:
            if len(order) >= r:
                for _course in list(itertools.combinations(order, r)):
                    _course = tuple(sorted(list(_course)))
                    if _course not in dic_course:
                        dic_course[_course] = 1
                    
                    else:
                        dic_course[_course] += 1
       

上記コード生成を実行するdic_course出力は以下の通り.

countが完了するまで、問題の条件をチェックすることはできません.すなわち、重複メニューの数は2より大きくなければなりません.そのため、値は1も含まれます.dic_course鍵の長さにより、最も価値のある鍵を見つける必要がある
まずlen(key)(昇順)とvalue(降順)で並べ替えます.
以下のとおりです.dic_course = sorted(dic_course.items(), key = lambda x : (len(x[0]), -x[1]))次にdic courseで答えに対応するキーを探し、見つけたらsortを行いstring typeに変換し、答えに挿入します.このようにdic courseを巡回し、答えの要素がすべて埋め込まれた後、ソート(response)を返します.
コードは以下の通りです.

now_len = len(dic_course[0][0])
max_cnt = dic_course[0][1]

for key , val in dic_course:
    if val == 1: continue
    if len(key) > now_len:
        max_cnt = val
        now_len = len(key)
        answer.append("".join(sorted(list(key))))
    
    elif len(key) == now_len:
        if max_cnt == val:
            answer.append("".join(sorted(list(key))))
        
    answer = sorted(answer)
                    
    return answer

完全なコード

import itertools


def solution(orders, course):
    answer = []
    # 조합이라니...
    # n_C_r
    dic_course = dict()
    while course:
        r = course.pop(0)

        for order in orders:
            if len(order) >= r:
                for _course in list(itertools.combinations(order, r)):
                    _course = tuple(sorted(list(_course)))
                    if _course not in dic_course:
                        dic_course[_course] = 1

                    else:
                        dic_course[_course] += 1

    dic_course = sorted(dic_course.items(), key=lambda x: (len(x[0]), -x[1]))
    # print(dic_course)

    now_len = len(dic_course[0][0])
    max_cnt = dic_course[0][1]

    for key, val in dic_course:
        if val == 1: continue
        if len(key) > now_len:
            max_cnt = val
            now_len = len(key)
            answer.append("".join(sorted(list(key))))

        elif len(key) == now_len:
            if max_cnt == val:
                answer.append("".join(sorted(list(key))))

    answer = sorted(answer)

    return answer