[백준 11286] 절댓값 힙

문제

이번 문제는 전체 연산을 반복할 수를 입력받은뒤, 값을 저장하거나 출력하는 문제이다.

0이 입력되면 배열에 저장된 절대값이 가장 작은 값을 출력한다.

이 때 저장된 절대값이 작은것이 여러개면 그냥 가장 작은 값을 출력한다.

0이 들어왔는데 배열이 비어있는 상태면 0을 출력하도록 한다. 

0 이외의 수가 입력 되었을 경우에는 입력된 값을 배열에 저장한다. 

알고리즘

1. 반복할 횟수를 입력받는다

2. 양수를 저장하는 우선순위 큐, 음수를 저장하는(단, 양수용 큐는 내림차순, 음수용은 오름차순) 우선순위 큐를 선언하여 0 외의 값이 들어왔을 때 저장한다

3. 0이 들어왔을 경우 각 음수,양수 큐가 비어있는 지 확인하고 둘다 비어있으면 0, 하나만 비어있으면 비어있지 않은 것에서 가장 작은 값을 출력한다

4. 둘다 비어있지 않은 경우 절대값 끼리의 비교를 통해서 절대값이 작은 값을 출력 시킨다

코드

#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;

int main() {
	//입출력 시간 단축
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	priority_queue<int,vector<int>, greater<int>> pq_p; //양수를 위한 큐-> 내림차순
	priority_queue<int>pq_n;//음수를 위한 큐 -> 오름차순

	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		if (num == 0)//출력
		{
			if (pq_p.empty() && pq_n.empty())//배열이 비어있는 경우
				cout << 0 << '\n';
			else if (pq_p.empty() && !pq_n.empty())//양수배열은 비어있는 경우
			{
				cout << pq_n.top() << '\n';//음수 배열에서 출력
				pq_n.pop();//배열에서 제거
			}
			else if (!pq_p.empty() && pq_n.empty())//음수배열은 비어있는 경우
			{
				cout << pq_p.top() << '\n';//양수 배열에서 출력
				pq_p.pop();//배열에서 제거
			}
			else {
				if (pq_p.top() < abs(pq_n.top()))//양수 절대값 값이 더 작은 경우
				{
					cout << pq_p.top() << '\n';
					pq_p.pop();//배열에서 제거
				}
				else if (pq_p.top() > abs(pq_n.top()))//음수 절대값이 더 작은 경우 
				{
					cout << pq_n.top() << '\n';
					pq_n.pop();//배열에서 제거
				}
				else if (pq_p.top() == abs(pq_n.top()))//양수 음수 절대 값이 더 작은 경우
				{
					cout << pq_n.top() << '\n';//음수 배열에서 출력 
					pq_n.pop();//배열에서 제거
				}
			}
			
		}
		else {//입력
			if (num > 0)//양수일 경우 양수 queue에 넣기
				pq_p.push(num);
			else if (num < 0)//음수일 경우 음수 queue에 넣기
				pq_n.push(num);
		}
	}
}

고찰

이번 문제는 절대 값 끼리의 비교를 위해 자동 정렬이되는 우선순위 큐를 사용하였다

출력시 값을 비교할 때 절대값끼리의 비교를 통해 같은 값이 있으면 더작은 값 즉, 음수 값을 출력해야하는 것이 관건이라 그냥 큐를 두개 사용하여 음수용, 양수용을 나누어 사용했다

이때 고려해야 할 점은 둘 중 하나가 비었을 때 처리 하는 것을 빼먹으면 메모리 접근 오류가 발생할 수 있다