[programmers/Python/hip]-もっと辛い


ソース:https://programmers.co.kr/learn/courses/30/lessons/42626?language=python3
すべての食べ物のスコビル指数はK以上に達しなければならない.
このため、スコビエル指数が最も低い2つの食品を以下のような特殊な方法で混合して新しい食品を製造した.
Leoは、すべての食べ物のスコビル指数がK以上になるまでかき混ぜます.
混合食品のスコヴェル指数=最も辛くない食品のスコヴェル指数+(第2の辛くない食品のスコヴェル指数*2)
Scoville:Leoが持つ食べ物のScoville指数の配列
K:欲しいスコビル指数
solution関数:すべての食べ物のスコビル指数をKより大きくするために、混合しなければならない最小回数return

私の答え

  • scovilleをバイナリminheap
  • に変換
  • min、スタックの根がKになるまで攪拌した.
    (2つの食べ物を取り出してかき混ぜて1つ入れる)
  • import heapq
    
    def solution(scoville, K):
        answer = 0
        
        heapq.heapify(scoville)
    
        while scoville[0] < K:
            heapq.heappush(scoville, heapq.heappop(scoville) + heapq.heappop(scoville) * 2)
            answer += 1
    
        return answer
    いくつかのテストケースでランタイムエラーが発生しました.pop要素がないときにpopを譲ると、実行時エラーが発生します.私はこの部分を処理していないことに気づきました.問題を見てみると、条件もそうです.

    だからコードを修正して、heapの中の要素の数が2より小さいならば、ポップアップしないで、直接-1を返します.
    import heapq
    
    def solution(scoville, K):
        answer = 0
        
        heapq.heapify(scoville)
    
        while scoville[0] < K:
            if len(scoville) < 2:
                return -1
            heapq.heappush(scoville, heapq.heappop(scoville) + heapq.heappop(scoville) * 2)
            answer += 1
    
        return answer