https://www.acmicpc.net/problem/11286
문제
> 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.
1) 배열에 정수 x (x ≠ 0)를 넣는다.
2) 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.
> 프로그램은 처음에 비어있는 배열에서 시작하게 된다.
접근
우선순위 큐를 사용하여 조건의 연산을 구현한다.
문제해결
> 우선순위 큐에서 세번쨰 인수로 사용할 비교 함수객체인 cmp를 정의해준다.
조건대로 abs를 통해 절대값을 구하고 절대값이 같다면 두 수 중에서 더 작은수가 우선순위가 높아 앞에오고,
절대값이 다르면 절대값이 더 작은 값이 앞에온다.
> 우선순위 큐를 선언해준다. 세번째 인수로 앞서 정의한 cmp를넣어준다.
> 입력으로 0이 들어왔을 때와 아닐 때를 먼저 나눠주고
0일때 만약 큐가 비어있다면 0을 출력하고 안비어있으면 큐의 맨 앞에 있는 값을 출력하고 그 값을 제거한다.
> 0이 아니면 들어온 값을 push해서 큐에 넣어준다.코드
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
struct cmp
{
bool operator()(int a, int b)
{
if (abs(a) == abs(b))
return a > b;
return abs(a) > abs(b);
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
priority_queue<int, vector<int>, cmp> pq;
while(N--)
{
int t;
cin >> t;
if (t == 0)
{
if (pq.empty())
{
cout << 0 << '\n';
continue;
}
cout << pq.top() << '\n';
pq.pop();
continue;
}
pq.push(t);
}
}
후기
우선 순위 큐를 처음 다뤄봤다. 생각보다 까다롭다.
서번째 인자인 cmp는 sort와 다르게 "타입"이기 때문에 함수가 올 수 없다. 그래서 구조체나 클래스를 통해 정의해줘야한다. struct를 통해 일단 선언하고 operator를 통해 마치 함수처럼 쓸 수 있게 함수객체로 만들어준다.
그리고 내부 정렬기준도 sort와 다르다. 여기선 compare(a, b)로 저 조건이 쓰인다.
그래서 a>b에 대해 true가 나오면 a의 우선순위가 더 낮다 라는 뜻이므로 b(더 작은수)가 우선순위가 높아 top에 위치하게 된다. 만약 sort처럼 a<b로 써주면 true가 나온다면 a가 우선순위가 더 낮으므로 더 큰 수인 b가 top에 오게된다. 이부분 이해하는데 좀 걸렸다.
그리고 우선순위 큐를 선언하는데 두 번째 인자로 vector는 큐가 내부적으로 어떤 자료구조를 이용할지에 대한 인자이다. 즉 vector를 통해 자료구조를 처리한다는 뜻이다. 보통 vector를 사용한다고 한다.
