[문제]
크리스마스에는 산타가 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아다니며 아이들에게 선물을 나눠줄 것이다. ㅎ하지만 썰매는 그렇게 크지 않아 세계 곳곳에 거점들을 세워 그 곳을 방문하며 선물을 충전해 나갈 것이다. 또한, 아이들을 만날 때마다 자신이 들고있는 가장 가치가 큰 선물 하나를 선물해 줄 것이다.
차례대로 방문한 아이들과 거점지의 정보들이 주어졌을 때, 아이들이 받은 선물들의 가치들을 출력하는 문제이다. 만약 아이들에게 줄 선물이 없다면 -1을 출력하면된다.
N을 입력받은 후 다음 N개의 줄에는 a가 들어온다. 그 다음 a개의 숫자가 들어온다. 이는 거점지에서 a개의 선물을 충전하는 것이고, 그 숫자들이 선물의 가치이다. 만약 a가 0이라면 거점지가 아닌 아이들을 만난 것이다.
a가 0일 때마다, 아이들에게 준 선물의 가치를 출력하고. 줄 선물이 없다면 -1을 출력하면된다.
[사용 알고리즘]
우선순위 큐
[풀이 핵심]
- 풀이의 핵심은 입력을 받을때마다 정렬하는 것이 아니라, 우선순위 큐를 사용해서 항상 가장 가치가 높은 선물이 pq.top()에 오도록 만드는 것이다.
- a가 0일때는 아이를 만나 선물을 줘야되는 상황이므로 pq.top()을 출력해주고 pop해주면된다. 만약 줄 선물이 없을 경우에는 -1을 출력하면된다.
[코드]
//boj14235번_크리스마스 선물_자료구조(우선순위 큐)
#include<iostream>
#include<queue>
using namespace std;
int main() {
int N;
cin >> N;
priority_queue<int> pq;
for (int i = 0; i < N; i++) {
int a;
cin >> a;
if (a == 0) {
if (pq.empty()) {
cout << -1 << '\n';
}
else {
cout << pq.top() << '\n';
pq.pop();
}
}
else {
for (int j = 0; j < a; j++) {
int gift;
cin >> gift;
pq.push(gift);
}
}
}
return 0;
}
