반응형
<코드>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int N, x;
priority_queue<int,vector<int>,greater<int>> pq1; // 양수 오름차순 저장
priority_queue<int> pq2; // 음수 내림차순 저장
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> x;
if (x == 0)
{
// 둘다 비어있다면
if (pq1.empty() && pq2.empty()) cout << "0\n";
else // 둘중 하나가 비어있거나 둘다 원소가 있거나
{
if (pq1.empty())
{
cout << pq2.top() << '\n';
pq2.pop();
}
else if (pq2.empty())
{
cout << pq1.top() << '\n';
pq1.pop();
}
else
{
if (pq1.top() < -pq2.top())
{
cout << pq1.top() << '\n';
pq1.pop();
}
else
{
cout << pq2.top() << '\n';
pq2.pop();
}
}
}
}
else if (x > 0) // 양수일 때
{
pq1.push(x);
}
else // (x < 0)음수일 때
{
pq2.push(x);
}
}
}
풀이 방법
양수의 경우에는 우선순위 큐 pq1에 오름차순으로 삽입, 음수의 경우에는 우선순위 큐 pq2에 내림차순으로 삽입하여 음수와 양수를 따로 저장하여 풀이를 하였습니다.
반응형
'🧩PS > 🥈Nomal' 카테고리의 다른 글
[C/C++] 백준 10942번 - 팰린드롬? (DP) (0) | 2020.12.28 |
---|---|
[C/C++] 백준 1655번 - 가운데를 말해요 (최대 힙, 최소 힙) (0) | 2020.12.28 |
[C/C++] 백준 1927번 - 최소힙 (우선순위 큐 오름차순) (0) | 2020.12.27 |
[C/C++] 백준 11279번 - 최대 힙 (우선순위 큐) (0) | 2020.12.27 |
[C/C++] 백준 2293번 - 동전 1 (DP) (0) | 2020.12.25 |