힙 - 백준 11286번 절댓값 힙

www.acmicpc.net/problem/11286

11286번: 절댓값 힙

IDEA

 

아래 두가지 조건을 만족시키는 자료구조의 기능을 구현해주면 된다. 

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

우선순위 큐를 활용해 구현하였다. 

우선순위 큐에 배열을 넣어준 후 , 정렬 기준을 따로 정의해두었다.

절댓값을 기준으로 오름차순하고, 만약 절댓값이 같다면 진짜 값이 가장 작은 수를 우선시하게 조건을 세웠다.

0이 아닌수가 들어오면 그냥 push 하고 0이 들어오면 가장 작은 값이 top인것을 이용하여 pop을 진행해 그 값을 배열에서 제거해주었다. 

 

우선순위 큐는 sort에서 사용자 함수 정의하듯이 하면 안된다,,,,, 

✨✨구조체를 구현해 연산자를 오버로딩시켜줘야하낟. 꼭꼮꼮 기억할 것✨✨

특히 bool operator() 이부분

struct compare {
	bool operator()(int a, int b) {
		if (abs(a) == abs(b)) return a > b;
		return abs(a) > abs(b);
	}
};

CODE

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

struct compare {
	bool operator()(int a, int b) {
		if (abs(a) == abs(b)) return a > b;
		return abs(a) > abs(b);
	}
};
priority_queue<int, vector<int>, compare>q;

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int num;
		scanf("%d", &num);
		if (num != 0) q.push(num);
		else {
			if (q.empty()) printf("0\n");
			else {
				printf("%d\n", q.top());
				q.pop();
			}
		}
	}
}