[백준] 11286번 절댓값 힙 문제풀이

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

11286번: 절댓값 힙

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

아이디어

우선순위 큐의 특성을 이용하여 자료구조 내의 원소들을 절댓값 기준으로 오름차순 정렬, 절댓값이 같다면 작은 값부터 출력하도록 하는 비교함수를 설정하여 풀 수 있습니다.

우선순위 큐란 어떠한 우선순위를 기준으로 정렬하는 자료구조로 그 기준을 설정할 수 있습니다.

만약 아무런 기준을 설정하지 않는다면 큰 값부터 정렬이 되고 비교함수를 통해 우선순위를 설정하면

그 우선순위에 따라 정렬됩니다.

priority_queue<int, vector<int>, 비교함수> 이름;

 

 

소스코드

#include <iostream>
#include<queue>
using namespace std;
int N;
struct cmp//swap여부 결정하는 비교함수
{
    bool operator()(int a, int b)
    {
        if(abs(a)==abs(b)) //절댓값이 같다면 작은 값부터 앞에 정렬
        {
            if(a>b) return true;
            else return false;
        }
        else if(abs(a)>abs(b)) return true;// 절댓값이 작은 값이 앞에 정렬
        else return false;
    }
};
priority_queue<int,vector<int>,cmp> pq;//우선순위 큐 설정
int main()
{
    int N; scanf("%d",&N);
    for(int i=0;i<N;i++)
    {
        int x; scanf("%d",&x);
        if(x!=0) pq.push(x);
        else
        {
            if(pq.empty())printf("0\n");
            else
            {
                printf("%d\n",pq.top());
                pq.pop();
            }
        }
    }
    return 0;
}

 

- 최대 힙 : https://nomadsjh.tistory.com/42

- 최소 힙 : https://nomadsjh.tistory.com/53