문제 20

C++ Priority Queue

내 상태: 미제출
난이도: 20번 문제 난이도 보기

Silver II
출제자: rlatjwls7882
시간 제한: 1000 ms
메모리 제한: 1024 MB

태그 보기

구현우선순위 큐자료 구조

처음에 빈 우선순위 큐 $P$가 있다. $Q$개의 쿼리를 순서대로 처리하라.

쿼리는 다음 중 하나이다.

push x: $P$에 정수 $x$를 추가한다.
pop: $P$의 가장 큰 원소를 삭제한다.
top: $P$의 가장 큰 원소를 출력한다.
size: $P$의 크기를 출력한다.

pop, top 쿼리는 항상 올바른 상태에서만 주어진다.

입력

첫 번째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 100\,000)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.

쿼리에 포함되는 정수 $x$의 범위는 다음과 같다. $(-10^9 \le x \le 10^9)$

출력

top, size 쿼리마다 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

10
push 3
push 7
push 5
top
pop
top
size
push 10
pop
top

예제 출력 1

공식 해설 풀이 스포일러 보기 접기

매번 전체를 정렬하면 삽입과 최댓값 삭제가 반복될 때 느려진다. 부모 값이 자식 값 이상인 최대 힙을 사용하면 루트에 항상 최댓값이 놓인다.

같은 값도 별개로 저장하여 삭제 한 번에는 하나만 제거한다.

삽입·삭제는 $O(\log(Q+1))$, 최댓값·크기 조회는 $O(1)$이다. 전체 시간복잡도는 $O(Q\log(Q+1))$, 공간복잡도는 $O(Q)$이다.

구현 · 언어별 풀이

C++ 구현

C++에서는 기본적으로 최대 힙인 priority_queue<int>를 사용한다. 추가·삭제·최댓값·크기는 각각 push(x), pop(), top(), size()로 처리한다.

C 구현

int 배열에 최대 힙을 구현한다. 삽입한 값을 부모와 교환하며 올리고, 루트 삭제 후 마지막 값을 더 큰 자식과 교환하며 내린다.

Python 구현

heapq는 최소 힙이므로 -x를 넣는다. 부호를 바꾸면 값의 대소관계가 뒤집히므로 최댓값은 -heap[0]으로 얻고, 삭제는 heappop(heap)으로 처리한다.

import heapq

heap = []
heapq.heappush(heap, -x)
top = -heap[0]
heapq.heappop(heap)

Java 구현

PriorityQueue<Integer>는 기본적으로 최솟값을 꺼내므로 Comparator.reverseOrder()로 비교 방향을 뒤집는다. offer(), peek(), poll(), size()를 사용한다.

PriorityQueue<Integer> heap =
    new PriorityQueue<>(Comparator.reverseOrder());
heap.offer(x);
int top = heap.peek();
heap.poll();

Rust 구현

BinaryHeap<i32>는 기본이 최대 힙이다. push(), peek(), pop(), len()을 사용한다.

use std::collections::BinaryHeap;

let mut heap = BinaryHeap::<i32>::new();
heap.push(x);
let top = *heap.peek().unwrap();
heap.pop();

JavaScript 구현

Node.js 표준 라이브러리에는 우선순위 큐가 없으므로 숫자 배열로 최대 힙을 구현한다. 삽입은 맨 뒤의 값을 부모와 비교해 올리고, 삭제는 마지막 값을 루트로 옮겨 더 큰 자식과 비교해 내린다. top은 heap[0], size는 heap.length이다.

function push(x) {
    let i = heap.length;
    heap.push(x);
    while (i > 0) {
        const p = Math.floor((i - 1) / 2);
        if (heap[p] >= x) break;
        heap[i] = heap[p];
        i = p;
    }
    heap[i] = x;
}
function pop() {
    const x = heap.pop();
    if (heap.length === 0) return;
    let i = 0;
    while (i * 2 + 1 < heap.length) {
        let j = i * 2 + 1;
        if (j + 1 < heap.length && heap[j + 1] > heap[j]) j++;
        if (heap[j] <= x) break;
        heap[i] = heap[j];
        i = j;
    }
    heap[i] = x;
}

heap=[]을 만들고 명령에 따라 두 함수를 호출한다.

제출

언어