[202 Kao Blind]メニュー更新

今まで試したことのない問題を解決しました!!
これが組み合わせに関する問題であることは以前も知っていましたが.
正しい概念が確立されていないためか、解けていない.
まず問題はDFSの組み合わせで問題を解決することである.
他の解の大部分はitertoolsの組合せを用いて解いていることがわかる.
以前は解決できなかった問題が、コンセプトを決めてから、Python専用ライブラリを使わなくても十分に解決できることに気づき、高い達成感と満足感を得ました.

質問する

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

問題の解き方

単品メニューと単品メニューの数の組み合わせデータをディック郡に計算します.
(組み合わせた単品メニューは昇順に並べ、ディックシリーズにカウントします.)
(並べ替えなければ同じ単品メニューでも順序が異なる場合は別のメニューに計算されます.)

計算の結果、最大注文回数(少なくとも2回以上のメニュー)を求めます.
(2回未満の場合は、自分のもののみ注文)

計算結果では、最大注文回数に対応する単品メニューを正解の並びに追加します.

コード#コード#

comb=['']*10
def solution(orders, course):
    answer = []
    for c in course:
        res=dict()
        for o in orders:
            DFS(0, 0, o, c, res)
        max=2
        for x in res:
            if res[x]>=max:
                max=res[x]
        for x in res:
            if max==res[x]:
                answer.append(x)
    answer.sort()
    return answer

def DFS(L, s, o, c, res):
    if L==c:        
        key=''.join(sorted(list(''.join(comb))))
        res[key]=res.get(key, 0) + 1
    else:
        for i in range(s, len(o)):
            comb[L]=o[i]
            DFS(L+1, i+1, o, c, res)