[백준] 우선순위큐 - 1927번 최소 힙 java

문제

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

1927번: 최소 힙

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

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

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

 

풀이

최소 힙은 최소 값을 빠르게 찾는 자료구조로, 우선순위큐를 통해 구현한다.

자바에서 제공하는 PriorityQueue의 구조 자체가 기본적으로 최소힙을 기준으로 구현되기 때문에 단순하게 PriorityQueue를 이용하여 구현하면 문제를 쉽게 풀 수 있다.

 

⭐️cf) 최대 힙의 경우 이와 반대로 동작하기 때문에 큐에 들어가는 숫자 값에 -1을 곱하여 저장하고 같은 방식으로 풀면 된다.

https://red-mimmu.tistory.com/60

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

 

코드

package 우선순위큐;

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

//최소힙 : 최솟값을 빠르게 뽑는 자료구조 
//PriorityQueue가 기본적으로 최소힙 구조임 
//연산
//1. 배열에 자연수 x를 넣는다.(offer, add)
//2. 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거한다.(poll)
public class No1927_최소힙 {

	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());
		
		PriorityQueue<Integer> q=new PriorityQueue<>();
		
		for(int i=0;i<n;i++) {
			int num=Integer.parseInt(br.readLine());
			if(num==0) {
				if(q.isEmpty()) System.out.println("0");
				else System.out.println(q.poll());
			}
			else {
				q.add(num);
			}
		}
	}

}