백준 11286 절댓값 힙 c++ [컴공과고씨]

https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

 

문제 정리

0이 아니면 원소 추가.

0이면 추가된 원소 중 절대값이 가장 작은 원소를 출력 후 제거.

원소의 개수가 0일 경우 0이 입력되면 0을 출력.

 

문제 해결 방법

우선순위 큐를 떠올리면 간단하게 풀 수 있는 문제이다.

우선 순위 큐를 간단하게 보려면 

https://hagisilecoding.tistory.com/60?category=1050177 

위 링크에서 간단하게 어떤건지 볼 수 있다.

 

우선순위 큐에서 구조체와 operator 함수를 사용하여 정렬 구조를 바꾸어 준다.

그리고 입력 받은 것을 큐에 push 해주고 입력 값이 0이라면 큐가 비어있는지 확인 후 조건에 맞게 구현해 주면 됩니다.

 

전체 코드 

#include <iostream>
#include <queue>
#include <vector>
#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(){
    int n, x;
    priority_queue<int, vector<int>, cmp> q;
    vector<int> v;
    cin >> n;
 
    for (int i = 0; i < n;i++){
        cin >> x;
        if(x == 0){
            if(q.empty()){
                // 큐가 비어있을 때 0을 출력
                v.push_back(0);
            }else{
                v.push_back(q.top()); // 가장 작은 원소 출력
                q.pop(); // 제거
            }
        }else{
            q.push(x); // 원소 추가
        }
    }
 
    for (int i = 0; i < v.size(); i++){
        cout << v[i] << '\n'; // 정답 출력
    }
 
    return 0;
}