[백준] 11286번 - 절댓값 힙 (C++)

11286번: 절댓값 힙

 

문제

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

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

 

 

입력

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

 

 

 

출력

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

 

 

풀이과정

해당 문제를 어떻게 접근할까 고민을 하다가 우선순위 큐를 음수버전과 양수버전 2개로 나누어서 풀이를 진행하였다.

그냥 들어오는 값 자체에 절대값을 씌워버리면 이 값이 원래 양수였는지 음수였는지 확인할 방법을 모르겠어서 그렇게 진행을 하였다.

 

std::greater : 내림차순 정렬 ( 기본형, 큰값이 앞에 오는 방식 4, 3, 2, 1 ... )

std::less : 오름차순 정렬 ( 작은 값이 앞에오는 방식 1, 2, 3, 4 ... )

 

형식으로 정리를 하고 절대값이 작은 값을 먼저 출력을 해줘야하기때문에  음수에는 절대값을 씌워 양수와 비교하여 작은 값을 출력해주는 방식으로 코드를 진행하였다.

 

code

#include <iostream>
#include <algorithm>
#include <queue>

int		main(void)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	int n, temp;
	std::priority_queue <int, std::vector<int>, std::greater<int> > plusQue;
	std::priority_queue <int, std::vector<int>, std::less<int> > minusQue;
	
	std::cin >> n;
	for (int i = 0; i < n; i++)
	{
		std::cin >> temp;
		if (temp == 0)
		{
			if (plusQue.empty() && minusQue.empty()) {
				std::cout << "0" << "\n";
			}
			else {
				if (!plusQue.empty() && minusQue.empty()) {
					std::cout << plusQue.top() << "\n";
					plusQue.pop();
				}
				else if (plusQue.empty() && !minusQue.empty()) {
					std::cout << minusQue.top() << "\n";
					minusQue.pop();
				}
				else if (plusQue.top() < -minusQue.top()) {
					std::cout << plusQue.top() << "\n";
					plusQue.pop();
				}
				else {
					std::cout << minusQue.top() << "\n";
					minusQue.pop();
				}
			}
		}
		else 
		{
			if (temp < 0) minusQue.push(temp);
			else plusQue.push(temp);
		}
	}

	return (0);
}

 

후기

조건식에서 신경쓰고 생각할 부분들을 생각보다 많아서 나름 고전을 많이 했었던 거 같다.