우선순위 큐 (c++)

 

우선순위 큐에 대한 문제로 백준 11279, 1927, 11286, 1655번을 풀었다.

 

11279, 1927, 11286은 기본적인 우선순위 큐에 대한 문제

 

priority_queue<자료형> 변수명 

ex) priority_queue<int, vector<int>, greater<int>> : 오름차순 정렬 

push(element) : 원소 삽입

pop() : 맨앞 원소 삭제

top() : 맨앞 원소 반환

size() : 크기 반환

empty() : 비어있는 지(true or false)

이러한 기본함수만 알면 풀 수 있다.

 

하지만 1655번은 좀 어려웠다...

가운데 원소를 출력하는 문제였다. 처음에는 vector로 접근해서 sort()을 이용해 가운데 원소를 반환했는데 시간 초과가 나왔다.

priority_queue로 접근해야 하는데 priority_queue로는 중간 인덱스를 사용하지 못하고 오직 top 원소만 반환받을 수 있어서 좀 어려웠다.

 

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

1655번: 가운데를 말해요

priority_queue 를 이용해 중간값을 찾으려면 maxheap 과 minheap 두개를 만들어 풀면 중간 값을 찾을 수 있다.

 

1655.cpp

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<math.h>
#include<queue>
 
using namespace std;
 
 
 
int main() {
 
    priority_queue<int, vector<int>, greater<int>> minheap;
    priority_queue<int> maxheap;
    int n;
    cin >> n;
    int k;
    cin >> k;
    maxheap.push(k);
    cout << k <<"\n";
    for (int i = 1; i < n; i++) {
        int temp;
        cin >> temp;
        if (maxheap.size() > minheap.size()) {
            minheap.push(temp);
        }
        else {
            maxheap.push(temp);
            
        }
 
        if (maxheap.top() > minheap.top()) {
            int t = minheap.top();
            minheap.pop();
            minheap.push(maxheap.top());
            minheap.pop();
            minheap.push(t);
        }
        cout << maxheap.top();
        cout << "\n";
        
    }
 
}