データ構造優先キューの使用:Java
3874 ワード
データ構造優先キューの使用
優先キュー
一般的な
逆に、
Javaの優先キュー
Javaは、優先キューをライブラリとして実装し、
優先度
JavaのPriorityQueueでは、数値型データがデフォルトで低いほど優先度が高くなります.優先度を異なる基準で決定したい場合、または異なる資料型を使用する場合は、
数値データを処理するときに降順で並べ替えたい場合は、Collections.reverseOrder()メソッドを使用できます.
白駿-2846上り坂
上り坂の高さの中で、一番高い上り坂を選ぶのが問題です.
上り坂の高さを降順基準のPriorityQueueに並べ、一度Dequeueするだけで一番高い上り坂の高さが出力されます.
優先キュー
一般的な
큐(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());
}
}
Reference
この問題について(データ構造優先キューの使用:Java), 我々は、より多くの情報をここで見つけました https://velog.io/@mulgyeol/Data-Structure-우선순위-큐-활용하기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol