データ構造優先キューの使用:Java


データ構造優先キューの使用
優先キュー
一般的な큐(Queue)資料構造は、先入データが先出する先入先出の資料構造である.
逆に、우선순위 큐(Priority Queueは、データに優先度を付与し、最も優先度の高いデータから順に現れるデータ構造である.
Javaの優先キュー
Javaは、優先キューをライブラリとして実装し、java.util.PriorityQueueにインポートしました.
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
上記のように宣言すればよい.
優先度
JavaのPriorityQueueでは、数値型データがデフォルトで低いほど優先度が高くなります.優先度を異なる基準で決定したい場合、または異なる資料型を使用する場合は、Comparator 클래스またはComparable 인터페이스を使用することができる.
数値データを処理するときに降順で並べ替えたい場合は、Collections.reverseOrder()メソッドを使用できます.
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
アルゴリズムの問題で使用
白駿-2846上り坂
上り坂の高さの中で、一番高い上り坂を選ぶのが問題です.
上り坂の高さを降順基準のPriorityQueueに並べ、一度Dequeueするだけで一番高い上り坂の高さが出力されます.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Acmicpc_2846_오르막길 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		PriorityQueue<Integer> PriorityQueue = new PriorityQueue<>(Collections.reverseOrder());
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.valueOf(br.readLine());
		int[] road = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			road[i] = Integer.valueOf(st.nextToken());
		}
		
		int start = 0;
		int end = 1;
		int sum = 0;
		
		while(start < N &&end < N) {
			int height = road[end] - road[end-1];
			
			if(height > 0) {
				sum+=height;
				end++;
			}else {
				if(start != end-1) {
					PriorityQueue.offer(sum);
				}
				start = end;
				end = end+1;
				sum = 0;
			}
		}
		
		queue.offer(sum);
		System.out.println(queue.poll());
	}

}