[C++/STL] Priority_queue(PQ)

1. 우선순위 큐(Priority_queue)

우선순위 큐는 일반적인 큐에서 우선순위에 따라 값이 저장되는 자료구조이다. 삽입과 삭제가 일어나도 우선순위가 가장 높은 순서대로 유지되도록 한다.

2. 내장 함수

1. push(k) : k값을 삽입한다.
2. top() : 가장 상단에 있는 값을 반환한다.
3. pop() : top에 있는 원소를 삭제한다.
4. empty() : 값이 비어있는지 확인한다.
5. size() : 큐의 전체 크기를 반환한다.

3. 선언해보자 !

#include <queue> 

int main(){
	//기본 선언식. int자료형의 원소를 담으며 자동으로 값이 큰 순서대로 유지한다. 
	priority_queue<int> pq; 
	
    //반대로, 값이 작은 순서대로 유지하고싶다면?
    priority_queue<int, vector<int> greater<>> pq; 
}

4. 프로그래머스 - 명예의 전당(1)

k와 score의 vector가 주어졌을 때 k번째 이상인경우 k개의 인원만 유지하되, 값이 높은 순서대로 유지한다. 이때 매 회차별 가장 낮은 점수를 반환한다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    priority_queue <int, vector<int>, greater<int>> pq;
    
    for (int i=0; i<score.size(); i++){
        pq.push(score[i]);
        if (i>=k){
            pq.pop();
        }
        answer.push_back(pq.top());
    }
    
    return answer;
}

참고한 블로그
https://kbj96.tistory.com/15