もっと辛い(ヒップホップ、優先順位キュー)-PYTHON

問題の説明

辛いのが好きなLeoは全ての食べ物のScobile指数をK以上にしたいすべての食べ物のScobile指数がK以上になるように、LeoはScobile指数が最も低い2つの食べ物を以下のような特殊な方法で混合し、新しい食べ物を作った.
混合食品のスコヴェル指数=最も辛くない食品のスコヴェル指数+(第2の辛くない食品のスコヴェル指数*2)
Leoは、すべての食べ物のスコビル指数がK以上になるまでかき混ぜます.
Leoが持つ食べ物のスコヴェル指数とScoville指数がKに達したとき、すべての食べ物のスコヴェル指数をK以上に混合する最小回数を返す解関数を作成してください.

せいげんじょうけん

スコビルの長さは2以上1000000以下です.
Kは0より大きく、10000000より小さい.
scovilleの各要素は0または10万以下です.
すべての食べ物のスコビル指数をKより大きくすることができない場合は、−1を返す.

I/O例

scoville K return
[1, 2, 3, 9, 10, 12] 7 2

解法

まず,再帰関数を用いて解決する方法を採用した.

リストがKより低い要素だけが残っています.

上記のリストとk,cntを

shake関数に渡す
1入力されたリスト要素がkより小さいかどうかを確認する
2 sort後arr[0]+arr[1]*2に混合
3混合元素+arr[2:]
4 cnt + 1
5繰り返し

def shake (arr,k,cnt) :
    if len([a for a in arr if a < k]) == 0:
        return cnt
    cnt += 1
    arr.sort()
    shaked = [arr[0] + arr[1]*2] + arr[2:]
    return shake (shaked,k,cnt)
    
def solution(scoville, K):
    answer = 0
    new_scoville = [i for i in scoville if i < K]
    answer = shake(new_scoville, K,0)
    return answer

ただし、値は良好ですが、実行時にエラーや効率の問題が発生した場合はエラーです...結果が出た.😢

だから、もっと効果的な資料型を考えて、最も辛くない2番目の問題「辛味」を見て、順番が最も重要で、ソートがsortより速い構造は何ですか?思い出した.
そして、教室で優先順位キューがsortライブラリより速いと聞いたのを覚えています.
今すぐ検索を開始...
c++と同様に、優先度Q Pythonもラッキーにライブラリを提供してくれました!( heapqの詳細 )
heapqは他の言語のモジュールとは違って、とても感謝しているやつで、push、popなら自動的にソートされます.👍 (名前のようにオシャレな...やつ...🤘🖖)
だからアルゴリズムを再整理すると

空のリスト(heap)を生成します.

scovilleを優先キューに設定し、heapに格納します.

heapの最小値をkより大きくなるまで繰り返します
3-1. お尻が一番小さく、2番目の小さな要素が混ざっています.
3-2. cnt +1

自動ソート、追加コードなしで便利😁

import heapq
    
def solution(scoville, K):
    p_qeue = []
    cnt = 0
    for num in scoville : 
        heapq.heappush(p_qeue,num)
    
    while p_qeue[0] < K :
        
        try:
            heapq.heappush(p_qeue, heapq.heappop(p_qeue) + heapq.heappop(p_qeue) * 2)
        except IndexError:
            return -1
        cnt += 1
    return cnt