問題の説明

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

せいげんじょうけん

scovilleの長さは2以上100000以下である.

Kは0以下です.

scovilleの各要素は0または1000000未満です.

すべての食品のスコヴェル指数がKを超えない場合、−1を返す.

問題を解く

1.pop()メソッドの使用を試みる

効率テストがあるので、正確な論理を書くだけでは合格できません.
スコビル指数を求める方法とアルゴリズムの説明は問題にあり,説明に従って論理を構築すれば精度テストに合格できる.

def solution(scoville, K):
    answer = 0
    
    while min(scoville) < K:
        if len(scoville) == 1 and scoville[0] < K:
            return -1
        scoville = sorted(scoville, reverse=True)
        scoville.append(scoville.pop() + (scoville.pop() * 2))
        answer += 1
        
    return answer

論理自体は簡単です.しかし、採点結果により、効率テストが1つも合格しなかったことが確認された.

解決策を探す過程で,heapqモジュールを使用している人が多いことが分かった.
バイナリツリーとHeapqモジュール

2.heapqモジュールの使用を試みる

このモジュールを使用する前に,バイナリツリー構造とHeapqモジュールの使用方法を簡単に学習した.
その後に構成される論理は,既存のpop()メソッドを用いた論理とあまり変わらない.
論理に問題はありませんが、効率の問題が発生しただけなので、heapqモジュールを既存の論理に適用して再実行してみます.

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while scoville:
        if len(scoville) == 1 and scoville[0] < K:
            return -1
        else:
            new_ = heapq.heappop(scoville) + (heapq.heappop(scoville) * 2)
            heapq.heappush(scoville, new_)
            answer += 1
            if scoville[0] >= K:
                break

    return answer

まず、所与のscovilleリストをheap構造に変換し、scoville内に重複するwhile構文を作成します.
新しい食べ物を作る過程で,木には1つのノードしか残っておらず,スコビル指数がKより小さい場合に−1を返す論理を構成している.
そうでなければ、heapppop()法により新しい食べ物を作成し、scovilleツリー構造に再添加する方法を繰り返し、ツリーの最小値がKより大きい場合、すべての食べ物がKより大きいためbreakで論理を完了する.

実行結果

採点結果