priorityqueue 3

[백준 11286] 절댓값 힙

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1. 연산의 개수 n을 입력받는다. 이후 n 만큼의 반복을 실행하는 for 반복문을 만든다. 2. 입력값에 따라 출력 후 값 삭제 or 값 list 에 추가 -> 를 실행한다. 2-1. 0을 입력 받았을 경우 : list 에서 절댓값이 가장 작은 값을 출력한다. 2-1-1. 절댓값이 가장 작은 값이 여러 개일 경우 : 가장 작은 수를 출력한다. - 이를 구현하기 위해 Prio..

[Solved]/BOJ 2023.04.28

[백준 1927] 최소 힙

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net Java 의 PriorityQueue 는 기본적으로 최소 힙을 사용한다. PriorityQueue 의 메서드들을 사용할 줄 알면 쉽게 풀 수 있는 문제이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue;..

[Solved]/BOJ 2023.04.28

PriorityQueue

PriorityQueue (우선순위 큐)는 우선순위에 따라 정리되어 있으며, 우선순위가 가장 높은 요소에 먼저 접근할 수 있는 자료구조이다. PriorityQueue 의 구현을 위해서는 Heap 이 사용된다. PriorityQueue는 기본적으로 Min Heap을 사용한다. 가장 높은 우선순위를 갖는 요소는 root 노드에 위치하게 된다. 이에 따른 요소의 추가와 삭제 과정은 다음과 같다. 추가 과정 새로운 요소를 Heap의 마지막 노드에 위치시킨다. 부모노드와 비교하며 적절한 위치에 배치한다. 삭제 과정 우선순위가 제일 높은 요소를 뽑는다. (root 노드) 이후 Heap의 마지막 노드를 root 노드의 위치로 이동시킨다. 자식노드와 비교하며 적절한 위치에 배치한다. PriorityQueue 클래스 메..