백준 11279 (Java) 최대 힙

백준 11279 - Silver 2

 

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

11279번: 최대 힙

 

문제

 

널리 잘 알려진 자료구조 중 최대 힙이 있다.

최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

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

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

 

입력

 

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.

다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다.

 

만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고,

x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다.

입력되는 자연수는 231보다 작다.

 

출력

 

입력에서 0이 주어진 회수만큼 답을 출력한다.

만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

예제입력

 

13
0
1
2
0
0
3
2
1
0
0
0
0
0

 

예제출력

 

0
2
1
3
2
1
0
0

 

이 문제는 2가지 조건만 충족되면 되는 문제이다.

주어지는 값이 0이면 가장 큰 값을 제거하고,

자연수라면 그 값을 배열에 넣는 형식이다.

 

여기서, 중요한 포인트는 가장 큰 값을 제거한다는 것이다.

값이 들어오면 순차적으로 들어오는 것이 정상적인 생각인데

큰 값이 계속 0번 인덱스에 들어오게 해야 한다는 것이다.

 

자바에서는 최소힙 또는 최대힙을 해결하기 위해서

우선순위 큐를 활용한다.

 

우선순위큐를 선언할 때, Collections.reverseOrder()를 활용하여서

큰 값이 가장 앞에 오게 하여서 문제를 해결하였다.

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Collections; import java.util.PriorityQueue;   public class Main{     public static void main(String[] args) throws IOException{         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         int n = Integer.parseInt(br.readLine());         StringBuilder sb = new StringBuilder();                  PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());                  for(int i = 0;i<n;i++) {             int x = Integer.parseInt(br.readLine());             if(x != 0) {                 pq.offer(x);             }             if(x == 0) {                 pq.offer(x);                 sb.append(pq.poll()).append("\n");             }         }         System.out.println(sb);     } }   Colored by Color Scripter

cs