문제
최대 힙을 구현하는 문제다. 자연수 x를 입력받으면 배열에 x를 넣고, 0을 입력받으면 배열에서 가장 큰 값을 출력한 뒤 그 값을 제거한다. 배열이 비어있을 때 0을 입력받으면 0을 출력한다.
입력
- 첫째 줄: 연산의 개수 N (1 ≤ N ≤ 100,000)
- 다음 N줄: 각 연산 값 (0이면 최댓값 출력, 자연수이면 삽입)
출력
0을 입력받은 횟수만큼 줄을 출력. 배열이 비어있으면 0, 아니면 최댓값 출력
예제
| 입력 | 출력 |
|---|---|
13 0 1 2 0 0 3 2 1 0 0 0 0 0 | 0 2 1 3 2 1 0 |
풀이
Java의 PriorityQueue는 기본적으로 최솟값이 먼저 나오는 최소 힙이다. 최대 힙을 구현하려면 Comparator를 역순으로 지정하여 최댓값이 먼저 나오도록 설정한다.
PriorityQueue를 역순 Comparator(o1, o2) -> o2 - o1으로 생성하여 최대 힙을 구현한다.- 입력값이 0이면 힙이 비어있는지 확인 후, 비어있으면 0을 출력하고 아니면
poll()로 최댓값을 꺼내 출력한다. - 입력값이 자연수이면
offer()로 힙에 삽입한다.
핵심 아이디어: Java PriorityQueue의 Comparator를 역순(o2 - o1)으로 설정하면 최대 힙으로 동작한다. 삽입과 삭제 모두 O(log N)의 시간복잡도로 처리된다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class Day35BOJ11279우선순위큐써보기 { // 11279
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
for (int i = 0; i < N; i++) {
int n = Integer.parseInt(br.readLine());
if (n == 0) {
if (queue.isEmpty()) {
System.out.println(0);
} else {
System.out.println(queue.poll());
}
} else {
queue.offer(n);
}
}
}
}복잡도
- 시간: O(N log N) — N번의 삽입/삭제 연산, 각각 O(log N)
- 공간: O(N) — 힙에 최대 N개의 원소 저장