https://www.acmicpc.net/problem/1927
문제
> 널리 잘 알려진 자료구조 중 최소 힙이 있다.
> 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
> 프로그램은 처음에 비어있는 배열에서 시작하게 된다.
> 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.
> 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다.
> 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고,
x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다.
> x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.접근
우선순위 큐를 사용해 큐에 수를 넣음과 동시에 최소값으로 정렬한다.
우선순위 큐의 세번째 인자를 정의해준다. sort와 다르게 이는 구조체나 클래스가 와야하므로 struct로 선언해주고
이 객체를 함수처럼 사용하기 위해 operator()가 필요하다. bool형으로 선언하고 문제에 조건을 정의해준다.
a와 b에 대해 a>b가 true면 등호의 왼쪽부가 우선순위가 "낮다"이므로 큐에서 뒤로 정렬이 된다.
false를 반환하면 등호 왼쪽이 우선순위 가"높으므로" 큐의 앞에 정렬이 된다.
즉, a가 b보다 크면 뒤로가고 크지 않으면 그대로 앞에 있는다.
문제해결
> x에 오는 수가 최대 2^31-1인데 이에 대한 연산이 없고 입출력만 다루므로 int형으로 선언해준다.
그리고 정렬 기준을 cmp로 정의해준다.
> 최소 힙이므로 작은 수가 앞에 와야한다. 그래서 조건으로 a>b를 return해준다.
이는 a가 b보다 크다면(true) a의 우선순위가 더 낮으므로 뒤로가고 작다면(false) 우선순위가 높아져 앞으로 오게된다.
> 이제 연산의 개수를 입력받고 연산을 처리한다.
x가 0일때 큐가 비었는지 안비었는지에 따라 0을 출력하거나, 큐에 가장 작은값(가장 앞에있는 top)을 출력한다.
그리고 pop으로 제거한다.
> 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);
priority_queue<int, vector<int>, cmp> pq;
int N;
cin >> N;
for (int i = 0; i < N; i++)
{
int x;
cin >> x;
if (x == 0)
{
if (pq.empty()) cout << "0" << '\n';
else
{
cout << pq.top() << '\n';
pq.pop();
}
}
else pq.push(x);
}
}
후기
예전에 절대 값 힙을 했었던 기억이 있어 우선순위 큐를 사용하는건 했는데 cmp에 대한 조건 처리가 모호했다.
먼저 구조체나 클래스가 와야하므로 이를 고려해 선언하고
다음으로 이 객체를 함수처럼 쓰기위해 operator()을 추가해 선언해줘야한다. 를 기억해야한다.
그리고 우선순위에 대한 정렬이므로 조건문에 대한 결과 또한 이해가 어려웠다. 조건문이 참이면 등호의 좌측이 우선순위가 낮은거고, 거짓이면 좌측이 높은것이다.
추가로 우선순위 큐는 최소 힙, 최대힙에 대해서 각각 cmp를 정의해주는게 아닌
greater<자료형>과 less<자료형> 으로 구현 할 수 있다.
그래서 위에 cmp를 지우고 cmp 자리에 greater<정수형>으로 해서 하니 정답이 나왔다.
