BOJ_11279_최대 힙

1

구분: 자료구조, 우선순위 큐

언어: Java

전략:

우선순위 큐를 활용한다. 

우선순위 큐는 작은 수부터 나오니 큰 수부터 나올 수 있도록 작업을 한다.

0의 개수만큼 숫자가 나와야 하므로, (빈 상태에서도) 일단 0을 넣고, 출력한다. 

---

2. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
        //큰 수부터 나오도록 하기 위해 이런 작업을 거침
		PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2) -> o2-o1);
		
		for(int i = 0; i<n; i++) {
			int num = Integer.parseInt(br.readLine());
			pq.add(num);
			if(num == 0) {
				System.out.println(pq.poll());
			}
		
		}
		
	}
}

---

3

• 우선순위 큐를 반전 시키는 방법을 오늘 처음 알게 되었다. -> 꼭 숙지하자
• 나는 처음에 바로 우선순위 큐를 이용해야 겠다고 생각했지만, 찾아보니 배열을 이용할 경우 시간초과가 난다고 한다
• Scanner를 사용하면 시간 초과가 난다.