스택/큐 프린터

https://programmers.co.kr/learn/courses/30/lessons/42587

코딩테스트 연습 - 프린터

 

PriorityQueue(우선순위 큐)

• Queue인터페이스의 구현체 중 하나로, 저장 순서와 상관없이 우선순위가 높은 것부터 꺼내진다. 
• 우선순위 큐는 숫자가 작은 요소일 수록 높은 우선순위를 매긴다.(숫자가 작을 수록 먼저 출력)
•  생성자에 각 요소의 우선순위를 비교할 기준인 Comparator를 매개변수로 전달하면 우선순위 판단 기준을 변경할 수 있다. 

---

1. PriorityQueue 객체 생성(기본)

public static void main(String[] args) {
	int[] arr = {5, 3, 7, 1, 9};
		
	PriorityQueue<Integer> queue = new PriorityQueue<>();
		
	for(int i:arr) {      // 우선순위 큐 요소 넣기
	    queue.add(i);
	}
		
	System.out.println(queue);   // 우선순위 큐 그대로 출력
    
        while(!queue.isEmpty()){
	    System.out.println(queue.poll());  // 우선순위 큐 요소 꺼내서 출력
}

[1, 3, 5, 7, 9]

1
3
5
7
9

---

1. PriorityQueue 생성자에 new Comparator<>()를 매개변수로 전달(내림차순)

public static void main(String[] args) {
	int[] arr = {3, 5, 7, 1, 9};
		
	PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<>() {
		public int compare(Integer o1, Integer o2) {
			return o2.compareTo(o1);
		}
	});
		
	for(int i:arr) {     
	    queue.add(i);
	}
		
	System.out.println(queue);  
    
        while(!queue.isEmpty()){
	    System.out.println(queue.poll());  
}

 

[9, 7, 5, 1, 3]
9
7
5
3
1

---

2. PriorityQueue 생성자에 Collections.reverseOrder()를 매개변수로 전달(내림차순)

public static void main(String[] args) {
	int[] arr = {1, 3, 5, 7, 9};
		
	PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
		
	for(int i:arr) {
		queue.add(i);
	}
		
	System.out.println(queue);
    
        while(!queue.isEmpty()){
	    System.out.println(queue.poll());
	}
}

[9, 7, 5, 1, 3]

9
7
5
3
1

• '우선순위가 높은 것부터 꺼낸다' 라는 의미! 우선순위가 높은 것 순으로 정렬하여 보관한다는 뜻이 아니다. 
• 그래서 그대로 출력했을 때와 실제로 요소를 하나씩 꺼내 출력했을 때 순서의 차이가 있을 수 있다. 

---

import java.util.PriorityQueue;
import java.util.Comparator;

public class printer {
	// 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발한다. 
	// 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼낸다. 
	// 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣는다. 
	// 그렇지 않으면 J를 인쇄한다.
	// 숫자가 클수록 중요도가 크기때문에 우선순위 큐를 생성한 뒤에 내림차순 정렬을 매개변수로 받는다. 
	// 중요도가 높은 문서 순으로, 해당 문서가 기존 대기 목록에서 어느 위치(몇 번째의)의 문서였는지 체크
	// location 위치의 문서일 때 -> 현재 출력 순번을 리턴
	// location 위치의 문서가 아닐 때 -> 출력 순번 증가, 다음으로 우선순위가 높은 문서 체크
   
	public int solution(int[] priorities, int location) {
       
		  int answer = 1;  // 출력순서 1부터 시작

	        // PriorityQueue를 이용해서 내림차순한 배열
	        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<>() {
	            public int compare(Integer o1, Integer o2) {
	                return o2.compareTo(o1);
	            }
	        });

	        // priorities[]에 있는 값을 queue에 집어넣기
	        for(int n: priorities) { 
	            queue.offer(n);
	        }

	        while(!queue.isEmpty()) {
	            for(int i=0; i<priorities.length; i+=1) {
	                if(queue.peek() == priorities[i]) { // (1)큐의 첫번째부분이 priorities배열의 부분과 같다면
	                    if(i == location) {// (2)priorities의 인덱스의 숫자가 location과 같다면 
	                        return answer;
	                }
	                answer++;  // 그 뒤를 비교하기 위해서 순번 증가 ++
	                queue.poll(); // queue에서 첫번째값 빼기(비교할 필요 xx) 다음으로 우선순위가 높은 문서 체크!
	                }
	            }
	        }
	   return answer;  
    }

}