[C++] BOJ #11286 절댓값 힙
Posted on 2022. 02. 17
문제
절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.
- 배열에 정수 x (x ≠ 0)를 넣는다.
- 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
입력
- 첫째 줄에 연산의 개수 N(1≤ N ≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 보다 크고, 보다 작다.
출력
- 입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.
1. 사용한 자료구조
- C++의
헤더파일 안에 있는 priority_queue를 사용하였다. priority_queue를 선언할 때, 정렬 기준을 정해주어야 하는데 여기서는 절댓값의 크기 비교를 위한 Custom Sort를 만들어서 넣어주어야 했다.
2. Priority Queue에서 Custom Sort는 어떻게?
priority_queue에서 Custom Sort를 하는 방법은 bool operator() 를 오버라이딩하여 사용하면 된다고 한다.- 여기서
()는 함수 호출 연산자이다. - C++은 객체 이름만으로 호출 가능한 함수를 만들 수 있으며, 이와 관련된 호출방법을 지원한다고 한다. 이 방법을 사용하기 위해서 준비된 키워드가
operator ()이다. 객체 이름의 함수를 클래스 정의 시 바로 적시할 수 없으므로 이런 키워드가 고안된 듯 하다고 한다. (출처 - https://wowcat.tistory.com/3060) - 다음으로,
priority_queue에서 사용하는greater<자료형>와less<자료형>은 다음과 같이 이루어져 있다.
template<class _Ty>
struct greater {
bool operator()(const _Ty& _Left, const _Ty& _Right) const {
return (_Left > _Right);
}
};
//less는 부등호 방향을 반대로 하면 됨
- 따라서, 우리도
구조체와operator () 오버라이딩을 이용하여 Custom Compare를 만들 것이다.
3. Priority Queue에서 Sort를 하는 방식
- 보통 예를들어
내림차순을 구현하는 compare 함수를 작성할 때에는 앞에 있는 원소가 뒤에 있는 원소보다 앞에 와야할 때 true를 리턴하도록 한다. - 하지만, Priority Queue는 다르다! Priority Queue의 top 원소는 container의 BACK에 있는 원소이기 때문이다.
(출처 - https://huilife.tistory.com/entry/C-Priority-Queue%EC%9D%98-custom-sort) - 따라서, 내림차순으로 정렬한다고 했을 때, container의 가장 마지막 원소가 가장 큰 원소여야 한다는 것이다. (그래서 전 게시물에서 최소 힙을 만들때도 비교함수 자리에
greater<int>를 썼었음) - 이번 문제는 "절댓값 최소 힙"이라고 부를 수 있으므로, Compare 구조체를 다음과 같이 만들어주겠다. 문제 조건에서 "절댓값이 같은 경우 음수를 먼저 출력"하도록 했으므로 container 상에서 양수가 음수 앞에 있어야 한다.
struct compare
{
bool operator()(int &A, int &B)
{
if (abs(A) == abs(B))
{
return A > B;
}
else
return abs(A) > abs(B);
}
};
4. 최종 소스코드
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
struct compare
{
bool operator()(int &A, int &B)
{
if (abs(A) == abs(B))
{
return A > B;
}
else
return abs(A) > abs(B);
}
};
int main()
{
priority_queue<int, vector<int>, compare> pq;
int N, x;
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
scanf("%d", &x);
if (x == 0)
{
if (pq.empty())
{
printf("0\n");
}
else
{
printf("%d\n", pq.top());
pq.pop();
}
}
else
{
pq.push(x);
}
}
}