[ 우선순위 큐 ] 개념 + 필수 과제 ( 백준 14235 크리스마스 선물 c++)

 

✅우선순위 큐

☑️ 우선순위가 높은 데이터가 먼저 나옴

- 큐(Queue) : 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out)

- 우선순위 큐(Priority Queue) : 큐와 달리, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.

( like. 롯데월드 매직패스 )

 

 

큐를 활용한 필수과제 문제 !

 

[  백준 14235 크리스마스 선물  ]

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    
    ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
    int n,a;
    priority_queue<int, vector<int>, less<int>> pq;
    //큰 것 부터 나오는 less<int>
    
    cin >> n;
    
    while(n--) {
        cin >> a;
        
        //아이들 만남
        if(a==0) {
            
            if (pq.empty()) { //줄 선물 없으면 -1 출력
				cout << "-1\n";
			} else{ //가장 가치 큰 선물이 맨 위로 정렬되어 있으니, top, pop!
			    cout << pq.top() << "\n";
				pq.pop();
			}
			
        } 
        
        //선물 충전
        else {
            for(int i=0; i<a; i++) {
                int gift=0;
                cin >> gift;
                pq.push(gift);
            }
        }
        
    }

    return 0;
}