백준 11279번 : 최대 힙, 백준 1917번 : 최소 힙

문제 접근

---

두 문제는 어떻게 트리를 구성하느냐의 차이이지 사실 상 같은 문제라고 할 수 있다. 처음에는 priority_queue 로 풀어보고, 직접 heap 을 구현해보고 싶어서 구현한 뒤 실행시켜봤다. 예제 케이스와 직접 만들어 본 테스트 케이스에서 잘 돌아가길래 제출해봤는데 '틀렸습니다' 가 나온다.

 

얼핏 생각해봤을때 이상한 부분이 없기도 하고 조금 피곤해서 잠깐 쉰 뒤 주석 달면서 코드 분석을 했다. 그런데 어머나 웬걸? 원소 삭제하는 함수에서 leaf 를 하나만 가지고 있는 원소가 있으면 오른쪽 leaf 가 없어서 계산에 허점이 생기고 바뀌지 않는다는 걸 알아차렸다! 해당 while 문의 조건을 바꾸고 내부적으로 break 하는 방식으로 바꿨고, 자식이 하나있는 경우는 while 문 외부에서 처리하도록 구현했다.

 

생각해보면 간단한건데 왜 그렇게 해맸는지 모르겠당.

 

아! 처음에 priority_queue 로 했을 때 시간 초과 나왔었는데 ios_base::sync_with_stdio(false); cin.tie(NULL) 넣으니까 해결되었다.

 

 

문제 코드 ( priority_queue 를 이용한 코드, 맞았습니다 )

---

#include <iostream>
#include <queue>

using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int N, x;
    // 최소 힙의 경우 priority_queue<int, vector<int>, greater<int>> heap;
	priority_queue<int> heap;
	
	cin>>N;
	
	while(N--)
	{
		cin>>x;
		
		if(x==0)
		{
			if(heap.empty())
				cout<<"0\n";
			
			else
			{
				cout<<heap.top()<<'\n';
				heap.pop();
			}
		}
		
		else
			heap.push(x);
	}
}

 

 

문제 코드 ( 최대 힙, 맞았습니다 )

---

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

using namespace std;

vector<int> heap;

// 확인용 print 함수
void print()
{
	cout<<"================\n";
	for(int i=0; i<heap.size(); ++i)
		cout<<heap[i]<<' ';
	cout<<"\n================\n";
}

//입력 함수
void insert_heap(int n)
{
	// cur 는 heap 에서 n의 현재 위치이고, push_back 되는 전의 heap.size() 와 같기 때문에 대입했다.
	int cur = heap.size();
	
	heap.push_back(n);
	
	// cur==0 이면 cur-1 에서 에러가 생기기에 초건을 추가했다.
	// 현재 위치의 부모와 비교를 해서 현재 자신이 더 크면 swap 하는 while 문이다.
	while(cur>0 && heap[cur]>heap[(cur-1)/2])
	{
		//print();
		swap(heap[cur],heap[(cur-1)/2]);
		cur=(cur-1)/2;
	}
}

void delete_heap()
{
	int cur = 0;
	
	//cout<<"Before Pop : Root is "<<heap[0]<<", Last element is "<<heap[heap.size()-1]<<'\n';
	swap(heap[0], heap[heap.size()-1]);
	heap.pop_back();
	
	// 해당 원소가 자식을 둘 다 가지고 있는지 확인한다.
	while(heap.size()>cur*2+2)
	{
    	// 자식이 모두 자신보다 작다면 break 한다.
		if(heap[cur] > max(heap[cur*2+1],heap[cur*2+2]))
		   break;
		
        // 보다 큰 자식과 swap 한다.
		if(heap[cur*2+1] >= heap[cur*2+2])
		{
			swap(heap[cur], heap[cur*2+1]);
			cur=cur*2+1;
		}
		   
		else
		{
			swap(heap[cur], heap[cur*2+2]);
			cur=cur*2+2;
		}
	}
	
    // 만약 자식이 하나 있는 원소가 남아있다면 크기 비교 후 swap 한다.
	if(heap.size()>cur*2+1)
	{
		if(heap[cur] < heap[cur*2+1])
			swap(heap[cur], heap[cur*2+1]);
	}
}

int main(void)
{
    ios::sync_with_stdio(false);
	cin.tie(NULL);
    
	int N, x;
	
	cin>>N;
	
	while(N--)
	{
		cin>>x;
		
		if(x==0)
		{
			if(heap.empty())
				cout<<"0\n";
			
			else
			{
				cout<<heap[0]<<'\n';
				delete_heap();
			}
		}
		
		else
			insert_heap(x);
	}
}

 

문제 코드 ( 최소 힙, 맞았습니다 )

---

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

using namespace std;

vector<int> heap;

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

void delete_heap()
{
	int cur = 0;
	
	swap(heap[0], heap[heap.size()-1]);
	heap.pop_back();
	
	while(heap.size()>cur*2+2)
	{
		if(heap[cur] < min(heap[cur*2+1],heap[cur*2+2]))
		   break;
		   
		if(heap[cur*2+1] <= heap[cur*2+2])
		{
			swap(heap[cur], heap[cur*2+1]);
			cur=cur*2+1;
		}
		   
		else
		{
			swap(heap[cur], heap[cur*2+2]);
			cur=cur*2+2;
		}
	}
	
	if(heap.size()>cur*2+1)
	{
		if(heap[cur] > heap[cur*2+1])
			swap(heap[cur], heap[cur*2+1]);
	}
}

int main(void)
{
    ios::sync_with_stdio(false);
	cin.tie(NULL);
    
	int N, x;
	
	cin>>N;
	
	while(N--)
	{
		cin>>x;
		
		if(x==0)
		{
			if(heap.empty())
				cout<<"0\n";
			
			else
			{
				cout<<heap[0]<<'\n';
				delete_heap();
			}
		}
		
		else
			insert_heap(x);
	}
}