[코딩테스트 고득점 Kit] 힙

문제 링크

더 맵게

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        Queue<Integer> queue = new PriorityQueue<>();
        
        for(int i : scoville) queue.add(i);
        
        while(queue.peek() < K) {
            if (queue.size() == 1) {
                return -1;
            }
            answer++;
            int s1 = queue.poll();
            int s2 = queue.poll();
            queue.add(s1 + s2*2);
        }
        return answer;
    }
}

스코빌 값을 우선순위 큐에 오른차순으로 넣고 계산 후 다시 큐에 넣는 방법으로 쉽게 풀었다.

디스크 컨트롤러

import java.util.*;

class Solution {
    
    class Job {
        int req;
        int time;
        
        public Job(int req, int time) {
            this.req = req;
            this.time = time;
        }
    }
    
    public int solution(int[][] jobs) {
        
        int answer = 0;
        Queue<Job> queue = new PriorityQueue<>(new Comparator<Job>() {
            // 큐에는 작업이 요청되는 시점 순으로 정렬되어 들어감
            @Override
            public int compare(Job j1, Job j2) {
                return j1.req - j2.req;
            }
        });
        
        for(int[] job : jobs) {
            queue.add(new Job(job[0], job[1]));
        }
        
        Queue<Job> temp = new PriorityQueue<>(new Comparator<Job>() {
            // 작업 시간의 오름차순으로 정렬
            @Override
            public int compare(Job j1, Job j2) {
                return j1.time - j2.time;
            }
        });

        int now = 0;  // 현재 시점
        while(!queue.isEmpty()) {
            // 현재 시점보다 같거나 작은 시점의 job 들을 꺼내온 후 소요시간 순으로 정렬
            while(!queue.isEmpty() && queue.peek().req <= now) {
                Job j = queue.poll();
                temp.add(j);
            }
            
            if(temp.isEmpty()) {
                now++;
                continue;
            }
            // answer에는 (index - 해당 job의 요청시점) + 소요시간
            // index += 소요시간
            Job job = temp.poll();
            answer += now - job.req + job.time;
            now += job.time;
            // 나머지는 다시 큐에 집어 넣음
            while(!temp.isEmpty()) {
                Job j = temp.poll();
                queue.add(j);
            }
        }
        
        return answer/jobs.length;
    }
}

Job class 를 만들어 요청시간, 작업시간을 저장했다.
우선순위 큐를 두개 만들어 하나는 요청시간을 오름차순으로, 하나는 작업시간을 오름차순으로 정렬했다.
요청시간 기준으로 담은 큐를 기준으로 요청시간의 조건이 만족하면 작업시간이 제일 짧은 작업을 선택해서 진행하도록 했다.

이중우선순위큐

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        Queue<Integer> asc = new PriorityQueue<>();
        Queue<Integer> des = new PriorityQueue<>(Collections.reverseOrder());
        int size = 0;
        
        for(String op : operations) {
            if(size==0) {
                asc.clear();
                des.clear();
            }
            
            String[] arr = op.split(" ");
            int num = Integer.parseInt(arr[1]);
            
            if(arr[0].equals("I")) {
                asc.add(num);
                des.add(num);
                size++;
            }
            
            if(arr[0].equals("D")) {
                if(size==0) continue;
                
                size--;
                if(num==-1) {
                    asc.poll();
                    continue;
                }
                
                if(num==1) {
                    des.poll();
                }
            }
        }
        if(size==0) {
            return new int[]{0, 0};
        }
        int min = asc.poll();
        int max = des.poll();
        return new int[]{max, min};
    }
}

오름차순으로 정렬하는 큐, 내림차순으로 정렬하는 큐를 만들어 insert시엔 두 개의 큐에 모두 추가하고 삭제할때는 만약 최솟값을 삭제해야 한다면 asc에서 poll, 최댓값을 삭제해야 한다면 des에서 poll한다.
이 경우 작업을 최소화하기 위해서 실제 큐에 아무것도 없어야 하지만 한쪽만 삭제하다보니 남아있는 경우가 있다.
그래서 size변수를 추가해 0일 시 두 큐를 모두 초기화 해준다.

---

전에 스택/큐에서 우선순위 큐를 사용했어서 그런지 쉽게 풀었던 것 같다!