[BaekJoon] 1927 최소 힙 (java)

🔗 문제 링크

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


👨🏻‍💻 작성한 코드

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

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		
		PriorityQueue<Integer> heap = new PriorityQueue<>();

		
		for (int i=0; i<n; i++) {
			int x = Integer.parseInt(br.readLine());
			
			if (x != 0) {
				heap.offer(x);
			}
			else {
				if (heap.peek()!=null) {
					bw.write(heap.poll()+"\n");
				}
				else {
					bw.write(0+"\n");
				}
			}
		}
		bw.flush();
		bw.close();
	}
}



📝 정리

자바에서 제공하는 라이브러리인 PriorityQueue는 일반적으로 최소힙과 같은 동작을 하여서 이번 문제는 PriorityQueue를 사용하여 간단하게 풀었다.

다른 사람들의 상위권에 위치한 성능 좋은 코드들을 보니 모두들 Heap구조를 직접 구현한 것을 확인할 수 있었다.

이를 보면 PriorityQueue자체가 메모리와 시간과 같은 성능 측면에서는 직접 구현한 코드들 보다 좋지는 않은것 같다.

좋은 웹페이지 즐겨찾기