반응형

<코드>

#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에 내림차순으로 삽입하여 음수와 양수를 따로 저장하여 풀이를 하였습니다.

 

www.acmicpc.net/problem/11286

 

11286번: 절댓값 힙

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

 

반응형

+ Recent posts