[백준 알고리즘 c++] 문제 72. 절댓값 힙 11286

알고리즘

 

[문제]

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

배열에 정수 x (x ≠ 0)를 넣는다.
배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.

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

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

 

[나의 풀이]

문제
1. 절댓값 힙의 자료구조 
입력
1. 연산의 개수 N을 입력 받는다.
2. N만큼 반복문을 돌린다.
2-1. 0이 아니라면 배열에 값 추가
2-2. 0이라면 절댓값이 가장 작은 값을 출력하고 배열에서 제거
2-2-1. 절대값이 가장 작은값이 여러개면 가장 작은수를 출력한다.
처리
출력
1. 0입력 횟수만큼 답을 출력한다. (가장 작은값)
1-1. 비어있는데 절대값이 가장 작은 값을 출력하려고 하는 경우 0을 출력한다.

 

[소스 코드]

#include <iostream>
#include <queue>

using namespace std;

int main()
{
	//
	// 문제
	// 1. 절댓값 힙의 자료구조 
	// 입력
	// 1. 연산의 개수 N을 입력 받는다.
	// 2. N만큼 반복문을 돌린다.
	// 2-1. 0이 아니라면 배열에 값 추가
	// 2-2. 0이라면 절댓값이 가장 작은 값을 출력하고 배열에서 제거
	// 2-2-1. 절대값이 가장 작은값이 여러개면 가장 작은수를 출력한다.
	// 처리
	// 출력
	// 1. 0입력 횟수만큼 답을 출력한다. (가장 작은값)
	// 1-1. 비어있는데 절대값이 가장 작은 값을 출력하려고 하는 경우 0을 출력한다.

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N = 0;
	cin >> N;

	//0면 마이너스임
	priority_queue<pair<int, int>> pq;

	for (int i = 0; i < N; i++)
	{
		int num = 0;
		cin >> num;

		//입력할 경우
		if (num != 0)
		{
			//마이너스일 경우
			if (num < 0)
			{
				pq.push({ num, 1 });
			}
			else 
			{
				num *= -1;
				pq.push({ num, 0 });
			}
		}

		//출력할 경우 
		else if (num == 0 && !pq.empty())
		{
			if (pq.top().second == 0)
			{
				cout << pq.top().first * (-1) << "\n";
			}
			else
			{
				cout << pq.top().first << "\n";
			}
			pq.pop();
		}
		else
		{
			cout << 0 << "\n";
		}
	}


	return 0;
}

다른 풀이)

#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);
		}
	}

}

 

[피드백]