[アルゴリズム]プログラマー-もっと辛い(Heap)

7769 ワード
アルゴリズム#アルゴリズム# テキストリンク

1.質問


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

2.制限

  • scovilleの長さは2以上100000以下である.
  • Kは0以下です.
  • scovilleの各要素は0または1000000未満です.
    • すべての食品のスコヴェル指数がKを超えない場合、−1を返す.

    3.解答

  • 優先キュー
  • listにスコヴェル指数の小さい順序でスコヴェルを入れます
    -前の最小のスコビル指数は
    • であった.
  • listの要素はいずれもスコビルより大きいか、
    • を繰り返してKより小さいlistの要素が1つしか残っていないまで繰り返します.
  • while文からlistの前の2つの要素を取り出し、スコビル式に代入し、listを再挿入します.
    (優先キューであるため自動ソート)
    ->ループごとに回答を増やす+->回数

    • 4.コード

    
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
		//모든 원소가 K이상인지 확인하기 용
		int check = 0;
		
		//새로 계산한 스코빌
		int ms=0;
		
		//가장 작은 스코빌
		int ls = 0;
		//두번쨰로 작은 스코빌
		int tls = 0;
		
		
		PriorityQueue<Integer> list = new PriorityQueue<>();
		
		
		for(int tmp : scoville) {
			list.add(tmp);
		}
		
		while(true) {
			check = 0;
			
			if(list.peek()>K) {
				break;
			}
			else if(list.size()==1 && list.peek()<K) {
				answer = -1;
				break;
			}

			
			ls = list.poll();
			tls = list.poll();
			ms = ls+ (2*tls);
			
			list.add(ms);
			answer++;
		}
		
		return answer;
    }
}
    WebdriverのJavaScriptをクリックする問題!
    CloudTrailで操作ログを設定する