문제링크
https://www.acmicpc.net/problem/11286
문제
절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.
- 배열에 정수 x (x ≠ 0)를 넣는다.
- 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
입력
첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -2^31보다 크고, 2^31보다 작다.
출력
입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.
조건
- 시간 제한 : 1s
- 메모리 제한 : 256MB
해설
우선순위 큐 시리즈의 문제이다. 특징은 절댓값을 이용한다는 것.
일단 절댓값이 작은 순서대로 출력을 하려고 하며, 입출력이 동시에 번갈아가며 이루어지기 때문에, 우선순위 큐를 이용해 자동으로 정렬을 해주는 것이 편리하다. 우선순위 큐는 가장 큰 값을 가장 앞으로 보내기 때문에 (내림차순) 절대값을 기준으로 가장 작은 값이 가장 앞으로 가는 오름차순으로 정렬해주기 위해서 양수에는 -1을 곱하고, 음수는 그대로 우선순위 큐에 push해준다.
그러나, 출력할 때 원래 양수였던 수면 +로, 음수였던 수면 -를 붙여서 출력해주어야 하기 때문에, 수의 부호를 구분할 수 있는 자료형을 쌍으로 묶어서 큐에 넣어준다. 나는 boolean 자료형을 이용해 해당 부호를 구분해주었는데, pair<int, bool> 등의 자료형을 이용하는 경우, 정수에 대해 정렬을 완료하고 나서, 같은 정수끼리는 bool 자료형으로 또 정렬을 하여 (false가 앞으로 간다) 부호끼리의 정렬은 따로 해주지 않아도 된다.
그후 처리해야할 과정은 최대 힙, 최소 힙 문제를 푸는 과정과 같다.
풀이
우선순위 큐는 <queue> 헤더파일에 저장되어 있다. 절대값을 저장할 int, 부호를 저장할 bool 자료형을 pair로 묶어서 우선순위 큐의 자료형으로 선언해준다.
#include <queue>
priority_queue<pair<int, bool>> pq;
절대값이 작은 순서대로 우선순위 큐의 가장 앞에 위치해야 하므로 오름차순 정렬을 위해 음수로 바꾸어 값을 push 해주어야 한다. 정수를 push하는 함수인 pushPQ 에서, 인자로 받은 정수가 음수이면 그대로, bool 값은 true로, 양수이면 -를 곱하고 bool 값은 false로 push 해준다.
void pushPQ(int v) {
if(v < 0) {
pq.push({v, true});
} else {
pq.push({-v, false});
}
}
Pop할 때는 함께 저장한 bool 값을 이용해 부호를 되살려 출력해준다. 양수는 음수로 저장되어 있으므로, 출력할 때 -1을 곱해주어야 한다. 큐가 비어있는 경우에는 그냥 0을 출력해주면 된다.
void popPQ() {
if(pq.empty()) {
cout << 0 << '\n';
} else {
if(pq.top().second == true) {
cout << pq.top().first << '\n';
}
else {
cout << -pq.top().first << '\n';
}
pq.pop();
}
}
코멘트
크게 어렵지 않은 문제!
코드
#include <iostream>
#include <queue>
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
using namespace std;
priority_queue<pair<int, bool>> pq;
void pushPQ(int v) {
if(v < 0) {
pq.push({v, true});
} else {
pq.push({-v, false});
}
}
void popPQ() {
if(pq.empty()) {
cout << 0 << '\n';
} else {
if(pq.top().second == true) {
cout << pq.top().first << '\n';
}
else {
cout << -pq.top().first << '\n';
}
pq.pop();
}
}
int main() {
FAST;
int N;
cin >> N;
for(int i = 0; i < N; i++) {
int k;
cin >> k;
if(k == 0) popPQ();
else pushPQ(k);
}
return 0;
}
Uploaded by Notion2Tistory v1.1.0