프로그래머스 디스크 컨트롤러 - Java (feat 우선순위 큐)

정리하는 김에 조금씩 공부했던 문제들 정리... 

 

🐟우선순위 큐 

- 단순 먼저들어오는 애가 먼저 나가는게 아님. 우선순위따라 자동 정렬된다. 

- 디폴트는 오름차순 정렬 

- 정렬 기준을 커스텀

 

만약 아래 처럼 입력이 들어온다고 하자. 

queue.add(new Node("나몰빼미", 6));
queue.add(new Node("염버니", 8));
queue.add(new Node("팽도리", 4));
queue.add(new Node("피카츄", 1));

결과는 이렇게 내림차순으로 출력하고 싶다

염버니 8
나몰빼미 6
팽도리 4
피카츄 1

 

방법 1 

PriorityQueue<Node> queue = new PriorityQueue<>((Node O1, Node O2) -> O2.size - O1.size);

방법 2 (자체 클래스에 compareTo 오버라이드) - 큐는 comparator없이 그냥 선언

static class Node implements Comparable <Node> {
        String name;
        int size;
    
        Node (String name, int size) {
            this.name = name;
            this.size = size;
        }
        
        public int compareTo(Node O) {
            return O.size - this.size;
        }
}

내림차순 출력하고 싶을 때는 target이나 2번째 대상에서 this 또는 1번째 매개변수 뺀다고 생각하자. 

---

피카츄 1
팽도리 4
나몰빼미 6
염버니 8

만약 위처럼 오름차순 정렬하고 싶다면? 

 

#1 ) 

PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(O -> O.size));

#2 )

PriorityQueue<Node> queue = new PriorityQueue<>((Node O1, Node O2) -> O1.size - O2.size);

#3 ) 

static class Node implements Comparable <Node> {
	    String name;
        int size;
    
        Node (String name, int size) {
        	this.name = name;
            this.size = size;
        }
        
        public int compareTo(Node O) {
            return  this.size - O.size;
        }
}

오름차순 출력하고 싶을때는 앞의 매개변수 혹은 this에서 뺀다고 생각 

 

 

---

🥕디스크 컨트롤러 

https://school.programmers.co.kr/learn/courses/30/lessons/42627

프로그래머스

프로세스(전체 작업) 담는 우선순위 큐는 request(요청 들어온 시간) 짧은 순서대로 정렬한다.

메모리(현재 작업중인 것들) 담는 우선순위 큐는 time(처리 시간) 짧은 순서대로 정렬한다. 

time이 작업 들어오는 시간 되면 메모리에 쭉 올림. 메모리에서는 자동으로 짧은것부터 처리하게 된다. 

answer에는 각 작업 당 (끝난 시간 - 들어온 시간)해서 모두 합해주고, 마지막에 작업 개수로 나눠줘서 정답 리턴.  

import java.util.*;
class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        int time = 0;
        PriorityQueue<Process> process = new PriorityQueue<>(Comparator.comparingInt(p -> p.request));
        PriorityQueue<Process> memory = new PriorityQueue<>(Comparator.comparingInt(p -> p.time));
        
        for (int i = 0; i < jobs.length; i++) {
            process.add(new Process(jobs[i][0], jobs[i][1]));
        }
        
        // 작업 목록 큐, 작업 중인 큐 둘중 하나라도 남아있다면 작업이 남은 것 
        while (!process.isEmpty() || !memory.isEmpty()) {
            // 작업이 남아있고 해당 요청이 들어온 상황이라면 memory에 올리기 
            while (!process.isEmpty() && process.peek().request <= time) {
                memory.add(process.poll());
            }
            
            // 메모리 비어있다면 다음 작업이 들어올 시간 될 때까지 대기 
            if (memory.isEmpty()) {
                time = process.peek().request;
            } else {
                Process p = memory.poll();
                time += p.time;
                answer += (time - p.request);
            }
            
        }
        
        return (answer / jobs.length);
    }
    
    public static class Process {
        int request;
        int time;
        
        public Process(int request, int time) {
            this.request = request;
            this.time = time;
        }
    }
}