개요

백준 11286: 절댓값 힙

• 입력
  첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

• 출력
  입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

접근 방식

1. 구현은 최소힙 최대힙 문제에서 했으므로 이번엔
   STL 안의 priority_queue를 이용해 문제를 해결했다.

2. 음수 양수가 동시에 들어와
   절대값을 비교해야하니 좀 편하게 하기위해
   음수 우선순위 큐, 양수 우선수위 큐를 미리 선언해줬다.

3. 음수 우선순위 큐는 절댓값이 작은 값이 top으로 가기 위해서
   우선순위를 less<int>로 설정해줬다.

   //양수만 담는 minHeap 우선순위큐
   priority_queue<int,vector<int>,greater<int>> positive_pq;
   //절댓값이 작은값을 가져오기 위해서 음수 우선순위큐는 maxHeap을 사용해야함
   priority_queue<int,vector<int>,less<int>> negative_pq;

전체코드

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

using namespace std;

//양수만 담는 minHeap 우선순위큐
priority_queue<int,vector<int>,greater<int>> positive_pq;
//절댓값이 작은값을 가져오기 위해서 음수 우선순위큐는 maxHeap을 사용해야함
priority_queue<int,vector<int>,less<int>> negative_pq;

void Input() {
	int N=0,tmp=0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		//음수 들어오면
		if (tmp < 0)
			negative_pq.push(tmp);
		//양수 들어오면
		else if (tmp > 0)
			positive_pq.push(tmp);
		//0 들어오면
		else if(tmp==0)
		{
			//만약 두 큐 다 비어있다면 0 출력
			if (negative_pq.empty() && positive_pq.empty()) {
				cout <<0<<'\n';
			}
			//음수큐 비어있다면 양수큐에서 제일 작은값 출력하고 pop
			else if (negative_pq.empty())
			{
				cout << positive_pq.top() << '\n';
				positive_pq.pop();
			}
			//양수큐 비어있다면  음수큐에서 top출력하고 pop
			else if (positive_pq.empty()) {
				cout << negative_pq.top() << '\n';
				negative_pq.pop();
			}
			//둘 다 차있다면
			else {
				//음수큐의 top의 절댓값이 양수큐의 top보다 작다면 
				if (-negative_pq.top() <= positive_pq.top()) {
					cout << negative_pq.top()<<'\n';
					negative_pq.pop();
				}
				//양수큐의 top이 더 작다면 
				else {
					cout << positive_pq.top()<<'\n';
					positive_pq.pop();

				}
			}
			
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
}

문풀후생

음수큐에선 우선순위를 반대로 설정해줘야한다는거 빼고는 무난했다.