우선순위 큐를 이용하는 문제이다. 우선순위 큐를 선언할 때 pair
를 사용해 절댓값과 원본값을 저장해주었고 오름차순으로 정렬되도록 greater
를 추가해주었다. 이렇게되면 top
에 절댓값과 원본값이 가장 작은 값이 있게되고 이를 출력 후 pop
해주었다.
우선순위 큐를 pair
를 사용함과 동시에 greater
를 사용한 것은 처음이라 찾아봤었다. 출력부분 \n
이 아니라 endl
로 해주니 시간초과가 났었다. 이부분을 조심하자.
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
int N, zero = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) {
int a;
cin >> a;
if (a != 0) {
pq.push({ abs(a), a });
}
else {
if (pq.empty()) {
cout << 0 << "\n";
}
else {
cout << pq.top().second << "\n";
pq.pop();
}
}
}
return 0;
}