Heap
더 맵게
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < scoville.length; i++) {
pq.add(scoville[i]);
}
// 1, 2, 3, 9, 10, 12
int cnt = 0;
// boolean flag = pq.peek().intValue() < K;
while(pq.peek().intValue() < K) {
if (pq.size() == 1) return -1;
int m1 = pq.poll();
int m2 = pq.poll();
int mix = m1 + m2*2;
pq.add(mix);
cnt++;
}
return cnt;
}
}
❌ 디스크 컨트롤러
import java.util.*;
class Solution {
public int solution(int[][] jobs) {
int flag = 0;
int time = 0;
int cnt = 0;
int idx = 0;
Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);
PriorityQueue<int[]> pq =
new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
while (cnt < jobs.length) {
while ((idx < jobs.length && flag >= jobs[idx][0])) {
// 값이 아니라 int[]를 넣었음.
pq.add(jobs[idx]);
idx++;
}
if (pq.isEmpty()) {
flag = jobs[idx][0];
}
else {
int[] temp = pq.poll();
time += temp[1] + flag - temp[0];
flag += temp[1];
cnt++;
}
}
return time/jobs.length;
}
}
이중 우선순위 큐
import java.util.*;
class Solution {
public int[] solution(String[] operations) {
// 1 2 3 4 5
PriorityQueue<Integer> min = new PriorityQueue<>();
//5 4 3 2 1
PriorityQueue<Integer> max =
new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < operations.length; i++) {
String s = operations[i];
if (s.equals("D 1")) {
if (max.isEmpty()) continue;
min.remove(max.poll());
} else if (s.equals("D -1")) {
System.out.println("cnt : " + i);
if (min.isEmpty()) continue;
max.remove(min.poll());
} else { // | 숫자 I
Integer j = Integer.valueOf(s.substring(2, s.length()));
max.add(j);
min.add(j);
}
}
int[] answer = new int[2];
if (min.isEmpty() && max.isEmpty()) {
answer[0] = 0;
answer[1] = 0;
return answer;
}
answer[0] = max.peek();
answer[1] = min.peek();
return answer;
}
}
// 다른 사람 풀이
import java.util.*;
class Solution {
public int[] solution(String[] operations) {
PriorityQueue<Integer> min = new PriorityQueue<>();
PriorityQueue<Integer> max =
new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < operations.length; i++) {
String s = operations[i];
if (s.equals("D 1")) {
if (max.isEmpty()) continue;
min.remove(max.poll());
} else if (s.equals("D -1")) {
System.out.println("cnt : " + i);
if (min.isEmpty()) continue;
max.remove(min.poll());
} else {
Integer j = Integer.valueOf(s.substring(2, s.length()));
max.add(j);
min.add(j);
}
}
int[] answer = new int[2];
if (min.isEmpty() && max.isEmpty()) {
answer[0] = 0;
answer[1] = 0;
return answer;
}
answer[0] = max.peek();
answer[1] = min.peek();
return answer;
}
}
Last updated