Beakjoon] 절댓값 힙 구현하기 (백준 11286 코테) = 우선순위

문제주소 : https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

 

 

풀이 : 연산의 개수때문에 O(n^2의 연산속도의 알고리즘으로 해결하면 안된다. O(nlogn) 시간복잡도의 알고리즘으로 풀어야 하며 값을 입력받으면서 바로바로 조건에 맞게 정렬시켜야 한다.
우선순위 큐를 이용하되 순서의 조건이 까다롭기에 조건을 직접 알려줘야한다.

 

 

 

코드는 아래 숨김

#include <iostream>
#include <queue>
#include <vector>

struct MyQueue {
	int val_;
	MyQueue(int val) : val_(val) {}

	bool operator<(const MyQueue q) const {
		if (std::abs(q.val_) < std::abs(this->val_))
			return true;
		else if ((std::abs(q.val_) == std::abs(this->val_))) {
			if (q.val_ < this->val_)
				return true;
			else
				return false;
		}			
		else
			return false;
	}
};


int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	std::priority_queue<MyQueue> pq;
	std::vector<int> result;


	int n;
	std::cin >> n;

	int temp_input;
	for (int i = 0; i < n; ++i) {		
		std::cin >> temp_input;
		if (temp_input == 0) {
			if (pq.empty())
				result.push_back(0);				
			else {
				result.push_back(pq.top().val_);
				pq.pop();
			}
		}
		else
			pq.push(temp_input);
	}

	for (auto iter = result.begin(); iter < result.end(); ++iter) {
		std::cout << *iter << "\n";
	}


	return 0;
}

 

알게 된 것 : 우선순위큐를 처음 써봤다..  STL을 공부하면서 정렬조건등을 커스텀해서 전달해주는 예제를 몇개 보긴 했었는데 이런식으로 쓰이게 되니 재미도 있고 신기했다.
책에서는 구조체의 () 오퍼레이터를 오버라이딩했는데 나의 경우엔 비교연산자를 오버라이딩하였다
*주의할 것 : 이미 비교연산자를 오버라이딩 했기에 그 내부에서 또 비교연산자를 쓰면 exception 오류가 발생하게 된다