728x90
반응형
★ 핵심 : Priority Queue는 우선순위가 있는 큐!
1. Java의 Priority Queue
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
}
}
· Java에서의 PriorityQueue 는 기본적으로 최소 우선순위 큐
· 자주 사용되는 메서드
1) add() - 우선순위 큐에 데이터 추가
2) size() - 현재 우선순위 큐에 들어있는 데이터의 수 반환
3) isEmpty() - 비어있으면 true, 아니라면 false
4) peek() - 최솟값에 해당하는 데이터 반환
5) poll() - 최솟값에 해당하는 데이터 반환 & 우선순위 큐에서 삭제
· 최대 우선순위 큐
1) - 를 붙여 관리 ← 파이썬에서는 이렇게 함
Ex) 우선순위 큐 원소 1, 2, 5가 있을 때 peek() 하면 1이 반환
원소들을 넣을 때 -1, -2, -5로 넣고 peek() 하면 -5가 반환되고 - 붙여서 최종 반환하면 5, 최대값이 반환
2) 자바에서는 또 다른 방법
class MaxPriorityQueueManager {
private PriorityQueue<Integer> pq;
public MaxPriorityQueueManager() {
pq = new PriorityQueue<>(Collections.reverseOrder());
}
//...
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
· 핵심
1. 최대 우선순위 큐이다.
→ - 을 붙여서 최대 우선순위 큐 구현
· 코드(Java)
import java.io.*;
import java.util.*;
class PriorityQueueManager {
private PriorityQueue<Integer> pq;
public PriorityQueueManager() {
pq = new PriorityQueue<>();
}
public void push(int n) {
pq.add(-n);
}
public int pop() {
if (pq.isEmpty()) {
return -1;
}
return -pq.poll();
}
public int size() {
return pq.size();
}
public int empty() {
return pq.isEmpty() ? 1 : 0;
}
public int top() {
if (pq.isEmpty()) {
return -1;
}
return -pq.peek();
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
PriorityQueueManager pqManager = new PriorityQueueManager();
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String cmd = st.nextToken();
if (cmd.equals("push")) {
int num = Integer.parseInt(st.nextToken());
pqManager.push(num);
}
if (cmd.equals("pop")) {
System.out.println(pqManager.pop());
}
if (cmd.equals("size")) {
System.out.println(pqManager.size());
}
if (cmd.equals("empty")) {
System.out.println(pqManager.empty());
}
if (cmd.equals("top")) {
System.out.println(pqManager.top());
}
}
}
}
※ 실력진단
PS. DP를 공부해야하는데 공부 못해서 점수가 항상 같다. DP푼지가 오래되가지고 기억이 잘 안 나더라. 다음 주는 연습해야할 것 같다.
728x90
반응형
'PS > 코드트리' 카테고리의 다른 글
[코드트리 챌린지] 8주차 - 그리디 (0) | 2023.10.30 |
---|---|
[코드트리 챌린지] 7주차 - 시뮬레이션(격자 안에서 단일 객체를 이동) (1) | 2023.10.23 |
[코드트리 챌린지] 5주차 - 그래프 탐색(DFS) (1) | 2023.10.09 |
[코드트리 챌린지] 4주차 - 그래프 탐색(BFS) (0) | 2023.10.02 |
[코드트리 챌린지] 3주차 - 2차원 바람 (0) | 2023.09.29 |