1. 더 맵게
우선순위 큐
1. PQ에 기본 자료구조형 넣어서 출력PriorityQueue<Integer>pq=new PriorityQueue<>(); //삽입 pq.add(5); pq.add(2); pq.add(1); // 출력 pq.peek(); // 값은 삭제되지 않음. (값 1만 출력) while (!pq.isEmpty()) { pq.poll(); // 1-> 2 -> 5 출력 (작은것부터 출력) }
- PQ에 Class 넣어서 출력
static class Book implements Comparable<Book> { int value; String writer; Book(int value, String writer) { this.value=value; this.writer=writer; } public int getValue() { return this.value; } public String getWriter() { return this.writer; } // 오름차순 정렬 (큰게 뒤로) @Override public int compareTo(Book book) { if (this.value>book.getValue()) return 1; else if (this.value<book.getValue()) return -1; return 0; } }적용
public static void main(String[] args) { PriorityQueue<Book> priorityQueue = new PriorityQueue<>(); priorityQueue.add(new Book(3650, "sds")); priorityQueue.add(new Book(31, "ds")); priorityQueue.add(new Book(1, "sjs")); priorityQueue.add(new Book(365, "hey")); while (!priorityQueue.isEmpty()) { Book book = priorityQueue.poll(); System.out.println("가격 : " + book.getValue() + " 작가 : " + book.getWriter()); } }
- 결과
가격 : 1 작가 : sjs
가격 : 31 작가 : ds
가격 : 365 작가 : hey
가격 : 3650 작가 : sds
해결방안
- PQ에 값을 넣어줌
- 이때 while문 돌때 PQ의 값을 2번 뽑을때는 조심 -> try Catch를 사용해서 문제 풀이
public int solution(int[] scoville, int K) {
int answer = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i : scoville) {
pq.add(i);
}
// 가장 작은것 뽑고 + 두번째로 작은것 *2 -> 다시 넣어줌 -> 이때 모든 지수가 K이상
int time = 0;
while (!pq.isEmpty()) {
// 가장 작은거 뽑음
int first = pq.poll();
// 이게 K이상인지 확인
if (first >= K) return time;
// 두번째를 뽑을수 있으면 뽑음 -> 못뽑으면 -1 return
try {
int second = pq.poll();
int res = first + second * 2;
pq.add(res);
time++;
if (pq.peek() >= K) {
return time;
}
} catch (Exception e) {
return -1;
}
}
return answer;
}2. 디스크 컨트롤러
문제
- 작업 요청 -> 작업 종료까지 걸린 시간의 평균을 가장 줄이는 방법 구하기
- 문제 예시는 FIFO로 되어 있어서 작업 시간이 많이 소요
- 해결방법은 작업소요시간이 가장 짧은것부터 처리?
- 요청시간이 길어지면 문제가 발생
- 따라서 요청시간이 가장 짧은것부터 일 처리 (오름차순 정렬)
- 이때 작업 시간이 짧은것부터 일처리 (오름차순 정렬)
[문제]
[FIFO]로 진행
FIFO) 예시 -> (3-0) + 11(요청1 ~ 3+9) +16(요청 2~ 12+6) => (3+11+16)/3 -> 10
[우선순위큐]로 진행
PQ) 예시 -> (3-0) + 7(요청2 ~ 3+6) +17(요청 1~ 9+9) => (3+7+17)/3 -> 9
How?
- 요청 시간이 가장 짧은 것을 선택하고 이 안에 진행할 수 있는 일들을 pq에 넣는다.
- Pq가 차면 작업기간이 가장 짧은것부터 일을 처리하고 time을 현재 시간과 더해서 갱신한다.
- Pq가 비워있으면 시간만 1 증가한다. (이때는 작업할 수 있는게 없다는 뜻)
import java.util.*;
class Solution {
public int solution(int[][] jobs) {
Info info;
// 큐에 넣기
// Queue<Info>queue=new LinkedList<>();
LinkedList<Info> queue = new LinkedList<>();
for (int i = 0; i < jobs.length; i++) {
System.out.println();
int req = jobs[i][0];
int end = jobs[i][1];
// System.out.println(req + "," + end);
info = new Info(req, end);
queue.offer(info);
}
// 넣은 큐를 정렬하기
Collections.sort(queue, new Comparator<Info>() {
@Override
public int compare(Info o1, Info o2) {
return o1.req - o2.req;
}
});
for (Info temp:queue) {
System.out.println("출력");
System.out.println(temp.req+" "+temp.time);
}
// 우선 순위 큐 만들기 - 우선순위큐에 넣을때는 Compare을 이용해 뒤에 인자를 바탕으로 정렬이 되어야 된다.
PriorityQueue<Info> pq = new PriorityQueue<>(new Comparator<Info>() {
@Override
public int compare(Info o1, Info o2) {
return o1.time - o2.time;
}
});
int answer=0;
int cnt=0;
int time=queue.peek().req; // 가장 짧은 요청 시간
while(cnt< jobs.length) {
//
while(!queue.isEmpty() && queue.peek().req<=time) { // 큐가 비어있지 않고, 요청시간 안에 들어 있으면
pq.offer(queue.poll()); // 큐에서 빼서 pq에 넣어줌, 이때 반복으로 넣어줌
}
if (!pq.isEmpty()) { // pq가 비어있지 않으면
Info temp=pq.poll(); // 그 값을 빼서 처리, 이때 빠진 값은 작업이 제일 빠른 거임
time+=temp.time; // 현재 시간에 + 더해줌
answer=answer+time-temp.req; // 누적 답에 현재 시간에서 요청 시간을 빼줌
cnt++; // 작업을 완료하였기 때문에 cnt 증가
}
else {
time++; // pq가 비어있으면 -> time 1 증가 (계속 시간 보내기 위해서)
}
}
answer=answer/cnt;
return answer;
}
}
class Info {
int req;
int time;
public Info(int req, int time) {
this.req = req;
this.time = time;
}
}3. 이중우선운위큐
우선순위큐는 기본적으로 작은 값부터 출력 됨 -> 큰 값부터 출력하기 위해서는? Collections.reverse() 사용
PriorityQueue<Integer>minPq=new PriorityQueue<>(); // 최소값 출력 PriorityQueue<Integer>maxPq=new PriorityQueue<>(Collections.reverseOrder()); // 최대값 출력문제
- 최대값, 최솟값을 구해야함으로 -> 2개의 우선순위큐를 사용하자 (하나는 최솟값, 하나는 최대값을 구하는 우선순위 큐 사용)
해결방법
-
2개의 우선순위 큐 생성 (min, max)
- 한쪽은 최소값을 나오게, 한쪽은 최대값이 나오게 하기 위해서
-
operations에 따라 연산자 확인 (Insert, Delete인지)
- operations을 split을 이용하여 연산자, 숫자로 나누기
-
operation에 따라
3-1. Insert면 minPq, maxPq에 둘다 값 넣어줌
3-2. Delete이고 만약 삭제값이 1(최대값이면) maxPq에서 값을 뺌, 이 값 또한 minPq에서 remove로 지워줌
3-3. Delete이고 만약 삭제값이 1(최소값이면) minPq에서 값을 뺌, 이 값 또한 maxPq에서 remove로 지워줌 -
나온값 확인 후 배열에 넣어준다.
import java.util.*;
class Solution {
public int[] solution(String[] operations) {
PriorityQueue<Integer>minPq=new PriorityQueue<>();
PriorityQueue<Integer>maxPq=new PriorityQueue<>(Collections.reverseOrder()); // 최대값 출력
for (String s:operations) {
String temp[]=s.split(" "); // 공백 반드시 써주기
String oper=temp[0];
String val=temp[1];
int value=Integer.parseInt(val);
// 삽입
if (oper.equals("I")) {
minPq.add(value);
maxPq.add(value);
}
// 삭제
else {
// 최대값 삭제
int removeValue;
if (value==1) {
// 만약 pq가 있으면 삭제
if (!maxPq.isEmpty()) {
removeValue=maxPq.poll(); // 최대값 삭제
minPq.remove(removeValue); // 최대값은 remove로 검색 후 삭제
}
}
// 최솟값 삭제
else {
// 만약 pq가 있으면 삭제
if (!minPq.isEmpty()) {
removeValue=minPq.poll(); //최소값 삭제
maxPq.remove(removeValue); // 최소값은 remove로 검색 후 삭제
}
}
}
}
System.out.println(maxPq.toString());
System.out.println(minPq.toString());
int[] answer = new int[2];
if (minPq.isEmpty()) {
answer[0]=0;
answer[1]=0;
}
else {
answer[0]=maxPq.poll();
answer[1]=minPq.poll();
}
return answer;
}
}REF
https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90
BackEnd Developer