[C/C++] 백준 1655번 - 가운데를 말해요 (최대 힙, 최소 힙)

 

 

 

<코드>

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

int N, x;
priority_queue<int, vector<int>, less<int>> maxheap;
priority_queue<int, vector<int>, greater<int>> minheap;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

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

		if (maxheap.size() == 0) maxheap.push(x);
		else
		{
			if (maxheap.size() == minheap.size())
				maxheap.push(x);
			else
				minheap.push(x);

			if (maxheap.top() > minheap.top())
			{
				int max_tmp = maxheap.top();
				int min_tmp = minheap.top();
				maxheap.pop();
				minheap.pop();
				maxheap.push(min_tmp);
				minheap.push(max_tmp);
			}
		}
		
		cout << maxheap.top() << '\n';
	}
}

 

풀이 방법

 

자료구조 힙(Heap)은 완전 이진트리의 일종으로 여러 값들 중에서 최댓값이나 최솟값을 빠르게 탐색하기 위해 만들어진 자료구조입니다.

여기서 최대 힙은 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진트리이고,

최소 힙은 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진트리를 뜻합니다.

 

이 문제에서는 최대한 빠르게 중간 값을 출력하기 위해 amxheap과 minheap이라는 우선순위 큐를 생성하여 maxheap은 내림차순으로, minheap은 오름차순으로 설정하였습니다. 

그리고 maxheap.top()이 항상 minheap.top() 보다 작거나 같도록 유지하고 maxheap.top() > minheap.top() 일 경우에는 두 값을 임시 변수에 저장한 다음 pop()한 뒤 서로 다른 우선순위 큐에 push 해줍니다.

이런 식으로 값들을 저장하게 된다면 maxheap의 top값은 항상 큐의 중간 위치 값이 됩니다.

 

 

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

 

참고 블로그 - dvlv.tistory.com/25