もっと辛い

問題の説明

辛いのが好きな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例
scovill K return
[1, 2, 3, 9, 10, 12] 7 2
I/O例説明
Scobile指数が1の食品と2の食品を混合し、食品のScobile指数は以下の通りである.
新しい食べ物のスコヴェル指数=1+(2)=5
食物を持つスコヴェル指数=[5,3,9,10,12]
スコヴェル指数が3の食べ物と5の食べ物を混合し、食べ物のスコヴェル指数は以下の通りである.
新しい食べ物のスコヴェル指数=3+(52)=13
食物を持つスコヴェル指数=[13,9,10,12]
すべての食品のスコビル指数は7以上で,このときの攪拌回数は2回であった.

アルゴリズム#アルゴリズム#

初めての試み

私の最初の考えはこうです.

最も辛くない食べ物と2番目に辛くない食べ物を混合し、1番目のインデックスに保存し、0番目のインデックスを削除します.

すべての食べ物のスコヴェル指数がK以上にならなければ、混合食品のスコヴェル指数が0であれば絶対にできない.

このような考えを持って書かれたコードは以下の通りです.

def solution(scoville, K):
    nlist = sorted(scoville)
    answer = 0

    if nlist[1] == 0:  #모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우 : 가장 맵지 않은 음식과 두 번째로 맵지 않은 음식의 스코빌 지수가 0일떄.
        answer = -1
        return answer

    while(nlist[0] <= K):
        nlist[1] = nlist[0] + 2 * nlist[1]
        del nlist[0]    # 가장 맵지 않은 음식과 두 번째로 맵지 않은 음식을 섞고, 1번째 인덱스에 저장한다음, 0번째 인덱스를 삭제해준다.
        nlist = sorted(nlist)
        answer += 1

    return answer

実行結果

失敗の原因は何ですか。

全ての食べ物のスコヴェル指数がKを超えられない場合は0を含む場合のみならず([3,3,3,3],200)のように混合してもスコヴェル指数がKを超えない場合があり、まったく考えられなかった.

ブレンド、マージ、ソート、ブレンド、ソート、それ自体が非常に非効率になります.Pythonに内蔵されているHeapqを使用するだけで、実行時間が大幅に減少します.

GoogleでHeapqを検索し、コードを書き直すことにしました.最初の試みと考えはあまり変わらなかったが、失敗の原因の最初の条件を増やした.

2回目の試み

正解

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)     #scoville 리스트를 힙으로 만든다.


    while 1:

        first = heapq.heappop(scoville) # 가장 맵지 않은 음식.
        if first >= K:  # 모든 음식의 스코빌 지수가 K이상임.
            break

        if len(scoville) <= 0:  # 원소가 하나만 주어졌는데 그게 K보다 낮을 때.
            answer = -1
            return answer

        second = heapq.heappop(scoville)   # 두 번째로 맵지 않은 음식.
        new = first + 2 * second

        if new == 0:    # new가 0이면 스코빌 지수를 K로 절대 못 만든다.
            answer = -1
            return answer

        heapq.heappush(scoville, new)
        answer += 1

    return answer

この問題はHeapを利用すれば簡単に解決できるが,脱出条件を考え出すのは厄介な問題のようだ.このコードも3回程度のいくつかのテスト例を誤って修正された.
基本条件以外の例外?考慮しなければならない脱出条件をリストアップすれば

1つの要素しか与えられず、K以上であれば0、K以下であれば-1でなければなりません.

混合されたスコヴェル指数が0であれば、Kは絶対にできません.続行する必要はありません

すべてのスコビル指数がKより大きいとき.

この3つの場合、コアは数量を考慮することです.コードをもっときれいに編むことができるはずですが、思いつくところに追加したので長くなったようです.