[C++] 백준11279 최대 힙

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
 
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
 
	int x = 0;
	std::cin >> x;
 
	std::multiset<int, std::greater<int>> multiset = {};
 
	for (int i = 0; i < x; ++i)
	{
		int iNumber = 0;
		std::cin >> iNumber;
 
		if (iNumber)
		{
			multiset.insert(iNumber);
		}
 
		else
		{
			if (!multiset.empty())
			{
				std::cout << *multiset.begin() << "\n";
				multiset.erase(multiset.begin());
			}
 
			else
			{
				std::cout << 0 << "\n";
			}
		}
	}
 
	return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
 
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
 
    int x = 0;
	std::cin >> x;
 
	std::priority_queue<int> priQue = {};
 
	for (int i = 0; i < x; ++i)
	{
		int iNumber = 0;
		std::cin >> iNumber;
 
		if (iNumber)
		{
			priQue.push(iNumber);
		}
 
		else
		{
			if (!priQue.empty())
			{
				std::cout << priQue.top() << "\n";
				priQue.pop();
			}
 
			else
			{
				std::cout << 0 << "\n";
			}
		}
	}
 
	return 0;
}

처음엔 Set으로 했다가 바로 시간 초과당해서 Que로 만들어서 했습니다.

근데 문제는 그게 아니라 tie(NULL)이랑 sync_with_studio(false)... ㅎㅎ....

Que로 했을 경우가 훨씬 싸게 먹혔습니다.

 

그 이유는

둘 다 정렬 기능을 가진 Tree형태의 자료구조이지만 내부 구조가 다릅니다.

priQue는 삽입과 삭제에 의해서 부모, 자식간의 우선순위는 확실하게 보장되지만, 양옆 노드와의 우선순위를 정의할 수 없습니다. 부모 노드는 자식 노드보다 우선순위가 높기 때문에 루트 노드가 최고 우선순위의 노드 라는 것"만" 보장합니다.

 

Set은 이진 트리 중 이진 '탐색' 트리 이기 때문에 노드의 위치만 파악할 수 있다면 위, 아래, 양옆 모든 노드와도 우선순위를 비교할 수 있습니다.