https://www.acmicpc.net/problem/11279
문제
> 널리 잘 알려진 자료구조 중 최대 힙이 있다.
> 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.
> 프로그램은 처음에 비어있는 배열에서 시작하게 된다.접근
우선 순위 큐를 사용하고 최대 힙이므로 정렬 기준을 조건이 참일 때 등호의 왼쪽에 있는 값이 우선순위가 낮은게 되므로
a < b를 return 해주도록 한다.
아니면 최소 힙은 우선순위 큐의 세번째 인자로 greater<자료형>을 사용하므로 최대 힙은 less<자료형>을 사용하여도 된다.
문제해결
> 문제의 입력이 int형의 범위 내로 가능하므로 우선순위 큐를 int형으로 선언해준다.
> 세번째 인자인 정렬 규칙을 구조체로, 함수처럼 사용하기위해 operator()로 선언하고 규칙을 정의해준다.
> 최대 힙 이므로 조건식이 참이 될 때 등호의 좌변이 우선순위가 낮게 되야하므로 a < b로 쓰면 더 작은 a가 뒤로가게된다.
> 처리할 명령의 수 N와 처리할 수 x를 입력받고 x에 따라 처리한다.
> x가 0이 아니면 우선순위 큐에 수를 넣고 0일땐, 큐가 비어있지 않다면 젤 앞에 있는 값을 출력하고 제거한다.
비어있다면 0을 출력한다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
//struct cmp
//{
// bool operator()(int a, int b)
// {
// return a < b;
// }
//};
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
priority_queue<int, vector<int>, less<int>> pq;
while (N--)
{
int x;
cin >> x;
if (x != 0)
{
pq.push(x);
continue;
}
if (!pq.empty())
{
cout << pq.top() << '\n';
pq.pop();
continue;
}
cout << "0" << '\n';
}
}
후기
정렬기준을 직접 써줄 때와, less<자료형>을 사용할 때 둘다 해봤다. 몇번 우선순위 큐를 해봐서 이제 이해가 됐고 감을 좀 잡은것 같다.
