백준 7662번 : 이중 우선순위 큐

문제 접근

---

최대 힙, 최소 힙 코드 응용해서 구현했는데 일단 테스트 케이스는 잘 돌아가고 제출 때 시간 초과가 나온다. 시간 복잡도를 계산해보니 insert 함수는 O(lgN) 인데, delete 함수는 find 함수로 인해 O(N) 이다. lower_bound() 사용 시 O(lgN) 에 찾을 수 있다고 해서 바꿔봤는데 시간 초과는 해결되어도 틀렸다고 나온다. 확인해보니 lower_bound() 는 정렬되어 있는 상태에서 목표값 n 보다 같거다 큰 원소의 주소를 반환하는 함수여서 정렬이 되어있어야 한다.

 

find() 함수를 직접 O(lgN) 으로 구현해보려고 했는데 방법이 없는 것 같다.

 

 

문제 코드 ( 시간 초과 )

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> maxheap;
vector<int> minheap;

// insert 함수의 시간 복잡도는 O(lgN)
void insert_maxheap(int n)
{
	int cur = maxheap.size();
	
	maxheap.push_back(n);
	
    while(cur>0 && maxheap[cur]>maxheap[(cur-1)/2])
	{
		swap(maxheap[cur],maxheap[(cur-1)/2]);
		cur=(cur-1)/2;
	}
}

void insert_minheap(int n)
{
	int cur = minheap.size();
	
	minheap.push_back(n);
	
    while(cur>0 && minheap[cur]<minheap[(cur-1)/2])
	{
		swap(minheap[cur],minheap[(cur-1)/2]);
		cur=(cur-1)/2;
	}
}

// delete 함수의 시간 복잡도는 O(N) -> find 함수의 시간 복잡도 O(N)
void delete_maxheap(int n)
{
	int cur = lower_bound(maxheap.begin(), maxheap.end(), n) - maxheap.begin();
	
	swap(maxheap[cur], maxheap[maxheap.size()-1]);
	maxheap.pop_back();
	
	while(maxheap.size()>cur*2+2)
	{
		if(maxheap[cur] > maxheap[cur*2+1] || maxheap[cur] > maxheap[cur*2+2])
		   break;
		   
		if(maxheap[cur*2+1] >= maxheap[cur*2+2])
		{
			swap(maxheap[cur], maxheap[cur*2+1]);
			cur=cur*2+1;
		}
		   
		else
		{
			swap(maxheap[cur], maxheap[cur*2+2]);
			cur=cur*2+2;
		}
	}
	
	if(maxheap.size()>cur*2+1)
	{
		if(maxheap[cur] < maxheap[cur*2+1])
			swap(maxheap[cur], maxheap[cur*2+1]);
	}
}

void delete_minheap(int n)
{
	int cur = lower_bound(minheap.begin(), minheap.end(), n) - minheap.begin();
	
	swap(minheap[cur], minheap[minheap.size()-1]);
	minheap.pop_back();
	
	while(minheap.size()>cur*2+2)
	{
		if(minheap[cur] < minheap[cur*2+1] || minheap[cur] < minheap[cur*2+2])
		   break;
		   
		if(minheap[cur*2+1] <= minheap[cur*2+2])
		{
			swap(minheap[cur], minheap[cur*2+1]);
			cur=cur*2+1;
		}
		   
		else
		{
			swap(minheap[cur], minheap[cur*2+2]);
			cur=cur*2+2;
		}
	}
	
	if(minheap.size()>cur*2+1)
	{
		if(minheap[cur] > minheap[cur*2+1])
			swap(minheap[cur], minheap[cur*2+1]);
	}
}

int main(void)
{
    ios::sync_with_stdio(false);
	cin.tie(NULL);
    
	int T, k, n;
	char com;
	
	cin>>T;
	
	while(T--)
	{
		maxheap.clear();
		minheap.clear();
		
		cin>>k;
		
		while(k--)
		{
			cin>>com>>n;
			
			if(com=='I')
			{
				insert_maxheap(n);
				insert_minheap(n);
			}
			
			else if(com=='D')
			{
				if(n==1 && !maxheap.empty())
				{
					delete_minheap(maxheap[0]);
					delete_maxheap(maxheap[0]);
				}
				
				else if(n==-1 && !maxheap.empty())
				{
					delete_maxheap(minheap[0]);
					delete_minheap(minheap[0]);
				}
			}
		}
		
		if(maxheap.empty())
			cout<<"EMPTY\n";
		else
			cout<<maxheap[0]<<' '<<minheap[0]<<'\n';
	}
}

 

 

문제 코드 ( 맞았습니다. )

---

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
	cin.tie(NULL);
    
	int T, k, n;
	char com;
	
	cin>>T;
	
	while(T--)
	{
		map<int,int> heap;
		
		cin>>k;
		
		while(k--)
		{
			cin>>com>>n;
			
			if(com=='I')
			{
				if(heap.find(n)==heap.end())
					heap.insert(make_pair(n,0));
				else
					++heap[n];
			}
			
			else if(com=='D' && !heap.empty())
			{
				map<int,int>::iterator it;
				
				if(n==1)
					it = --heap.end();
				
				else
					it = heap.begin();
				
				if(it->second==0)
					heap.erase(it);
				
				else
					it->second--;
				
			}
		}
		
		if(heap.empty())
			cout<<"EMPTY\n";
		else
			cout<<(--heap.end())->first<<' '<<heap.begin()->first<<'\n';
	}
}