[백준] 1927 최소 힙 - Data Structure / Java

• 문제 링크

1927번: 최소 힙

 

• 풀이 과정

문제에 제시된 조건 중 배열의 가장 작은 값을 선택하여 출력하기 위해 PriorityQueue 자료구조를 활용한다.

Integer 우선 순위 큐는 기본 값으로 오름차순, 즉 수가 작을수록 우선 순위가 높기에 매개변수를 변경하지 않는다.

 

입력 받은 x 가 0 이 아닐 경우 큐에 x 를 삽입하고,

x 가 0 일 경우 큐의 원소 존재 여부에 따라 0 을 출력할 지,

우선 순위에 의해 가장 작은 수를 꺼내어 출력할 지 결정하여 정답을 구한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;

public 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> q = new PriorityQueue<>();
		for (int i = 0; i < n; i++) {
			int x = Integer.parseInt(br.readLine());

			if (x == 0)
				if (q.isEmpty())
					bw.write(0 + "\n");
				else
					bw.write(q.poll() + "\n");
			else
				q.offer(x);
		}

		bw.flush();
	}

}