[C++/알고리즘] 백준 11279 (X)

 

 

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

 

 

 

 

 

 

계속 시간초과 오류가 발생하였다.

 

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

int main()
{
	int N;
	cin >> N;
	vector<int> arr;
	arr.reserve(N);

	for (int i = 0; i < N; i++)
	{
		int temp = 0;
		cin >> temp;

		if (temp == 0)
		{
			if (!arr.empty())
			{
				sort(arr.begin(), arr.end(),greater<int>());
				cout << arr[0] << "\n";
				arr.erase(arr.begin());
			}
			else
			{
				cout << "0" << "\n";

			}
		}
		else {
			arr.push_back(temp);
		}
	}
}

 

 

이게 처음에 작성한 코드이고 시간초과가 계속 발생해서 우선순위 큐로 바꿔봐야 하나?

하고 우선순위 큐로 다시 작성한 코드가 아래 코드이다.

 

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

int main()
{
	int N;
	cin >> N;
	priority_queue<int> arr;


	for (int i = 0; i < N; i++)
	{
		int temp;
		cin >> temp;

		if (temp == 0)
		{
			if (!arr.empty())
			{
				cout << arr.top() << "\n";
				arr.pop();
			}
			else
			{
				cout << "0\n";
			}
		}
		else {
			arr.push(temp);
		}
	}
	return 0;
}

1번에서는 6%대에서 2번에서는 31%대에서 시간초과 오류가 계속 발생한다.

어디서 뭘 더 어떻게 줄여야 하는지 잘 모르겠다; 

 

혹시 몰라서 C++14로 체크하던걸 C++11으로 바꿨지만 여전히 똑같았다.

우선순위 큐로도 해결되지 않는다면 이건 대체 어떻게 풀어야 하는 걸까... 

정말 문제 제목대로 힙을 구현해야만 해결할 수 있는 문제인가?

근데 아무리 그래도 우선순위 큐로 구현한 것도 시간초과가 뜨나?