[c++] 백준 11286, 절댓값 힙
알고리즘 분류 : priority queue (우선순위 큐)
입력받은 정수(0이 아닌)의 절댓값을 오름차순 정렬하고, 0을 입력받을 때마다 절댓값이 가장 작은 값을 출력하면 되는 문제다. (절댓값이 가장 작은 값이 여러 개일 때는, 가장 작은 수를 출력한다.)
문제를 해결하기 위해서 우선순위 큐 자료구조를 이용한다. 이때 우선순위 큐는 내림차순 정렬을 기본으로 하기에, 인자를 추가하여 오름차순 정렬하도록 만드는 과정이 필요하다.
priority_queue<pair<int,int>,vector<pair<int,int>>,compare> pq;
인자로 추가된, 비교 함수 compare는 pq가 first와 second를 모두 오름차순 정렬하도록 한다.
절댓값이 가장 작은 값이 여러 개일 때, 가장 작은 수를 출력한다는 조건 때문에, pq에 push하기 전, input이 음수인지 양수인지에 대한 판단이 필요하다.
input<0인 경우, first에 store, second에 0을 저장
input>0인 경우, first에 store, second에 1을 저장
출력의 과정에서는 만약 pq.top()의 second가 0이라면 -1을 곱해서 출력, pq.top()의 second가 1이라면 그대로 출력한다.
#include <iostream>
#include <queue>
using namespace std;
struct compare{
bool operator()(pair<int,int> a,pair<int,int> b){
if(a.first==b.first){
return a.second>b.second;
}
else return a.first>b.first;
}
};
priority_queue<pair<int,int>,vector<pair<int,int>>,compare> pq;
//first와 second를 모두 오름차순으로 정렬하는 pq
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
int input,store;
for(int i=0; i<N; i++){
cin >> input;
store=abs(input); //store는 input의 절댓값을 저장
if(input==0){
if(pq.empty()){
cout << 0 << '\n';
}
else{
if(pq.top().second==0){
cout << -1*pq.top().first << '\n';
}
else{
cout << pq.top().first << '\n';
}
pq.pop();
}
}
else{
if(input<0){
pq.push(make_pair(store,0)); //input<0인 경우, second에 0을 저장
}
else if(input>0){
pq.push(make_pair(store,1)); //input>0인 경우, second에 1을 저장
}
}
}
}
Author And Source
이 문제에 관하여([c++] 백준 11286, 절댓값 힙), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@landlala/c-백준-11286-절댓값-힙저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)