[プログラマー]もっと辛い

🔗 質問リンク

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

🤔 質問する

辛いのが好きなLeoは全ての食べ物のScobile指数をK以上にしたいすべての食べ物のScobile指数がK以上になるように、LeoはScobile指数が最も低い2つの食べ物を以下のような特殊な方法で混合し、新しい食べ物を作った.섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)Leoは、すべての食べ物のスコビル指数がK以上になるまでかき混ぜます.Leoが持つ食べ物のスコヴェル指数とScoville指数がKに達したとき、すべての食べ物のスコヴェル指数をK以上に混合する最小回数を返す解関数を作成してください.

📌 せいげんじょうけん

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

Kは0以下です.

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

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

😮 トラブルシューティング方法

最小Hip(優先キュー)を用いて,まず3つの条件を構築して問題にアクセスし,解決した.

キューの先頭要素(最小値)がK以上の場合

キューのサイズは1です.すなわち、scovilleアレイに要素が1つある場合、

です.

キューの先頭要素(最小値)はKより小さく、キューのサイズが1より大きい場合は

である.

PriorityQueue<Integer> pq = new PriorityQueue<>();
//우선 순위 큐에 데이터 넣기
for(int scv : scoville)
   pq.offer(scv);

優先キューに入る要素は常に完全バイナリツリー(最小hip)を構成し、最小値がツリーのルートに入り、要素をキューに挿入すると、常にツリーの終端ノードに入り、親ノードに比べて挿入要素が小さい場合はswapを行う.
👉🏻最初の条件の確認👈🏻10,7,8,5,9からなるscoville配列が与えられ、K値が5の例である.
キューに要素を挿入すると、ノードは{5,8,7,10,9}の順序で挿入されます.優先順位Qでは、先頭の元素は5であり、最小値はKに等しいので、食べ物を混ぜる必要はない.したがってcount(0)を返すだけでよい.

//큐 size가 1인 경우 값 비교만 필요
//큐의 가장 최소 값이 K 이상인 경우 음식 섞어줄 필요 x
while(pq.size()>1 && pq.peek() < K)

👉🏻2番目の条件を確認👈🏻
Qの大きさが1であればwhile文の条件を入れる必要がないので、食べ物を混ぜる必要はありません.したがって,値がKより大きいかどうかを比較し,−1またはcount(0)を返すだけでよい.

if(pq.peek() < K )
    return -1;

👉🏻3番目の条件をチェック👈🏻3,2,4,6,1からなるscoville配列が与えられ、K値が14の例である.
キューに要素を挿入すると、ノードは{1,2,4,6,3}の順序で挿入されます.優先順位行列では、最小の元素1と最小の元素2を問題の公式に従って食べ物を混合し、1+(2*2)=5にし、優先順位行列に入れる.もしそうなら、{2,3,4,6,5}になります.このように、先頭の要素がK以上になるまで繰り返し、繰り返し回数まで数えて返すとよい.
次はJavaで実装されたコードです.

🚩 JAVAコード

package com.algorithm.Programmers.Lv2;

import java.util.PriorityQueue;

public class Solution_42626 {
    public static void main(String[] args) {
        int[] scoville = {3,2,4,6,1};
        int k = 14;
        System.out.println(solution(scoville,k));
    }

    public static int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        //우선 순위 큐에 데이터 넣기
        for(int scv : scoville)
            pq.offer(scv);
        for(int s : pq)
            System.out.println(s);
        //큐 size가 1인 경우 값 비교만 필요
        //큐의 가장 최소 값이 K 이상인 경우 음식 섞어줄 필요 x
        while(pq.size()>1 && pq.peek() < K){
            int first = pq.poll();
            int afterScov = 0;

            //최소 값이 K 보다 작으면 음식 섞기
            if(pq.peek() < K){
                afterScov = first + (pq.poll() * 2);
                pq.offer(afterScov);
                answer++;
                continue;
            }

            //최소 값이 K보다 큰 경우 마지막으로 음식 섞어주기
            afterScov = first + (pq.peek() * 2);
            pq.offer(afterScov);
            answer++;
        }

        //최소 값이 기대 스코빌 지수보다 작으면 만들 수 없는 경우
        if(pq.peek() < K )
            return -1;

        return answer;
    }
}

📄 整理する

アルゴリズムを解く際に初めてHIP(優先キュー)を用いた.時間的複雑度はO(NLOGN)であり,それは最初に優先度の高い要素を処理し,バイナリツリー構造からなるからである.

最小または最大

要素の質問に適用すると、効率が高いはずです.

年ぶりのhipの再利用に伴い,hipの挿入・削除演算の構造を再考した.