[백준] 우선순위 큐 - 11279번 최대힙 java

문제

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

풀이

우선순위큐(PriorityQueue)를 이용하면 힙을 구현하지 않고도 문제를 해결할 수 있다.

우선순위큐는 우선순위가 높은 순서대로 원소를 삭제하는데, 원래 자바 라이브러리의 우선순위큐는 최솟값에 높은 우선순위를 부여하게 되므로(최소힙) -1을 곱해주는 방식으로 최대힙을 구현해보았다.

 

또 그 외에도 다양한 방법으로도 구현할 수 있는데

Queue<Integer> q=new PriorityQueue<>(Comparator.reverseOrder());

Queue<Integer> q=new PriorityQueue<>((o1, o2)-> o2-o1);

와 같은 식으로 우선순위큐를 선언한다면 -1을 곱해주지 않아도 최대힙으로 구현할 수 있다.

코드

1. 최소힙으로 최대힙 구현(-1을 곱함)

package 우선순위큐;

import java.io.*;
import java.util.*;
public class No11279_최대힙 {
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		Queue<Integer> q=new PriorityQueue<>();
		
		StringBuilder sb=new StringBuilder();
		
		for(int i=0;i<n;i++) {
			int k=Integer.parseInt(br.readLine());
			if(k==0) {
				if(q.isEmpty()) {
					sb.append(0+"\n");
				}else {
					sb.append(q.poll()*-1+"\n");
				}
			}else {
				//원래는 최소값을 삭제하기 때문에 최댓값을 삭제하기 위해선(최대힙으로 만들기 위해선) -1을 곱해준다 
				q.add(k*-1);
			}
		}
		
		System.out.println(sb.toString());
	}

}

2. 최대힙으로 구현

package 우선순위큐;

import java.io.*;
import java.util.*;
public class No11279_최대힙 {
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		//Queue<Integer> q=new PriorityQueue<>(Comparator.reverseOrder());
		Queue<Integer> q=new PriorityQueue<>((o1, o2)-> o2-o1);
		StringBuilder sb=new StringBuilder();
		
		for(int i=0;i<n;i++) {
			int k=Integer.parseInt(br.readLine());
			if(k==0) {
				if(q.isEmpty()) {
					sb.append(0+"\n");
				}else {
					sb.append(q.poll()+"\n");
				}
			}else {
				q.add(k);
			}
		}
		
		System.out.println(sb.toString());
	}

}