[Java/백준/우선순위 큐] 11279번: 최대 힙, 1927번: 최소 힙

 

자바의 우선순위큐 라이브러리에 원소를 담고 다시 빼면, 우선순위는 오름차순으로 정렬되어 나온다.

따라서 최대 힙을 구현하려면 우선순위 큐를 선언할 때, 매개변수로 Collections.reverseOrder()를 넣어주면 된다.

 

www.acmicpc.net/problem/11279

11279번: 최대 힙

 

import java.util.*;
import java.io.*;

class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
		StringBuilder answer = new StringBuilder();
		
		for(int i=0; i<N; i++) {
			int input = Integer.parseInt(br.readLine());
			if(input==0) {
				if(pq.isEmpty())
					answer.append("0\n");
				else {
					answer.append(Integer.toString(pq.poll())+"\n");
				}					
			}
			else
				pq.add(input);
		}
		
		bw.write(new String(answer));
		
		bw.flush();
	}
}

 

 

www.acmicpc.net/problem/1927

1927번: 최소 힙

 

 

 

import java.util.*;
import java.io.*;

class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		StringBuilder answer = new StringBuilder();
		
		for(int i=0; i<N; i++) {
			int input = Integer.parseInt(br.readLine());
			if(input==0) {
				if(pq.isEmpty())
					answer.append("0\n");
				else {
					answer.append(Integer.toString(pq.poll())+"\n");
				}					
			}
			else
				pq.add(input);
		}
		
		bw.write(new String(answer));
		
		bw.flush();
	}
}