백준[자바]_11279_1927_우선순위큐

오늘은 우선순위큐에 대한 기본적인 문제를 풀어보았다. 혹시라도 우선순위큐를 처음 들어본 사람은 아래의 링크로 들어가서 정리된 내용을 한 번 공부하고 오길 바란다.

https://cm-me0410.tistory.com/79

우선순위큐(Priority Queue)

오늘도 마찬가지로 한 문제을 풀이하려 했지만, 카테고리에 분류된 처음 두 문제가 너무 비슷하고 기본적인 문제이기 때문에 두 문제를 모두 풀이하도록 하겠다. 문제에 대한 링크를 아래에 걸어두도록 하겠다. 

우선순위큐

• 11279_최대힙
• 1927_최소힙

11279번: 최대 힙

1927번: 최소 힙

 

두 문제에 대한 풀이는 정말 코드 한 줄 차이라서 최대 힙을 기준으로 정리하겠다. 모두들 기본적으로 우선순위큐에 대한 개념을 확인하고 왔다는 가정 하에 서술하겠다. 특별히 우선순위 큐를 직접 구현하지 않고 자바에서 지원하는 라이브러리를 사용했다. 

[ 문제 접근 ]

• 우선순위큐를 사용하는 가장 기본적인 문제이다. 최대힙으로 구현하라는 말은 우선순위 큐의 우선순위를 가장 큰값이 가장 먼저 나오도록 하는것이다. 가장 큰 값이 가장 먼저? 맞다 내림차순이다.
• 그렇다면 최소힙이란 무엇일까? 우선순위를 가장 작은 값이 먼저 나오도록 하는 것이고, 이 말은 정렬기준을 오름차순으로 정해주어야 한다는 말이다. 
• 이쯤에서 어느정도 눈치를 채신 분들이 있을것이다. 우선 순위 큐의 가장 큰 메리트트 FIFO구조의 큐에서 값을 꺼낼 때, 우선 순위가 가장 높은 것을 먼저 뽑는다, 즉 꺼내는 순서를 바꿀 수 있다는 것이다. 
• 결국 우선 순위큐를 사용하기 위해서는 큐 내부에서 우선순위를 어떻게 부여할지에 대한 기준으로 반드시 우선순위를 지정해줄 정렬 조건을 따로 지정해주어야 한다.

 

[ 문제 풀이 ]

• 자바에서 지원하는 모든 라이브러리는 보통 기본적으로 오름차순 정렬이 default값이다. 그래서 내림차순으로 정렬하기 위해서 필자는 Collections 인터페이스에서 제공하는 reverseOrder()메소드를 사용해서 구현했다. 
• 입력값이 0이 아니라면 입력값을 그대로 큐에 넣는다. 
• 입력값이 0이라면, 큐에서 우선순위가 가장 높은 요소를 뽑는다. 이 때, 큐가 비어있다면 0을 출력한다. 

 

[ 11279_최대힙 ]

package Queue;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class _11279_PrioriQueue_최대힙 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer   sb = new StringBuffer();
        
        //질문의 개수
        int n = Integer.parseInt(br.readLine());
        
        //우선순위큐를 사용할때는 반드시 우선순위를 부여할 정렬기준을 만들어 줘야 한다. 
        //기본적으로 오름차순 -> 최소힙으로 되어 있기 때문에 최대 힙을 구현하기 위해서는 내림차순으로 정렬해야 한다. 
        Queue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
        
        for(int i=0; i<n; i++) {
            int num = Integer.parseInt(br.readLine());
            
            if(num==0) {//0이라면 가장 큰 값을 출력한다. 
                
                sb.append(pq.size() == 0 ? 0 : pq.poll()).append('\n');
                
            }else {//0이 아니라면 값을 그대로 넣는다.
                pq.add(num);
            }
        }
        
        System.out.println(sb.toString());
    }
 
}
 

[ 1927_최소힙 ]

package Queue;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class _1927_PrioriQueue_최소힙 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer   sb = new StringBuffer();
        
        //질문의 개수
        int n = Integer.parseInt(br.readLine());
        
        //우선순위큐를 사용할때는 반드시 우선순위를 부여할 정렬기준을 만들어 줘야 한다. 
        //기본적으로 오름차순 -> 최소힙으로 되어 있기 때문에 최대 힙을 구현하기 위해서는 내림차순으로 정렬해야 한다. 
        Queue<Integer> pq = new PriorityQueue<Integer>();
        
        for(int i=0; i<n; i++) {
            int num = Integer.parseInt(br.readLine());
            
            if(num==0) {//0이라면 가장 큰 값을 출력한다. 
                
                sb.append(pq.size() == 0 ? 0 : pq.poll()).append('\n');
                
            }else {//0이 아니라면 값을 그대로 넣는다.
                pq.add(num);
            }
        }
        
        System.out.println(sb.toString());
    }
 
}