[11286번] 절대값 힙

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 우선순위 큐

Priority Queue STL을 이용하여 두개의 pq를 구현하고 

두개의 힙에 양수와 음수를 구분하여 넣어줌으로써 절댓값을 구현한다.

소스 코드 주석에 나와있듯이 둘다 빈 경우, 하나만 빈 경우, 둘다 안 빈 경우로 구분하여 소스 코드를 완성하였다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

#include <iostream> #include <cstdio> #include <queue>   using namespace std;   priority_queue<int> pq1, pq2;   int main() {     int n, val;       scanf("%d", &n);       while (n--)     {         scanf("%d", &val);           if (val > 0)             pq1.push(-val);         else if (val < 0)             pq2.push(val);           else         {             // 둘다 빈 경우             if (pq1.empty() && pq2.empty())                 printf("0\n");               // 둘다 안 빈 경우             else if (!pq1.empty() && !pq2.empty())             {                 if (-pq1.top() >= -pq2.top())                 {                     printf("%d\n", pq2.top());                     pq2.pop();                 }                 else if (-pq1.top() < -pq2.top())                 {                     printf("%d\n", -pq1.top());                     pq1.pop();                 }             }               // pq1만 빈 경우             else if (pq1.empty() && !pq2.empty())             {                 printf("%d\n", pq2.top());                 pq2.pop();             }               // pq2만 빈 경우             else if (!pq1.empty() && pq2.empty())             {                 printf("%d\n", -pq1.top());                 pq1.pop();             }         }     }     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus