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;
    }
}