[Algorithm] 최소힙(priority_queue : 우선순위 큐)(c/c++)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

최대합 문제와 반대로 풀어보면 되겠다.

최대힙(max heap) 은 

1 2 3

priority_queue< int, vector<int>, less<int> > pQ; // OR priority_queue<int> pQ;

cs

최소합(min heap) 은

1

priority_queue< int, vector<int>, greater<int> > pQ;

cs

로 쓰인다.

#. Code

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

#include <cstdio> #include <vector> #include <queue> #include <algorithm>   using namespace std;   int main(void) {     freopen("input.txt", "rt", stdin);       int n;     priority_queue<int, vector<int>, greater<int> > pQ;       while (true)     {         scanf("%d", &n);           if (n == -1)             break;           if (n == 0)         {             if (pQ.empty())                 printf("-1\n");             else             {                 printf("%d\n", pQ.top());                 pQ.pop();             }         }         else             pQ.push(n);     }       return 0; } Colored by Color Scripter

cs

#. Other code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include<stdio.h> #include<queue> #include<vector> using namespace std;   int main(){     int a;     priority_queue<int> pQ;       while(true){         scanf("%d",&a);         if(a==-1) break;         if(a==0){             if(pQ.empty()) printf("-1\n");             else{                 printf("%d\n", -pQ.top());                 pQ.pop();             }         }         else pQ.push(-a);     }       return 0; } Colored by Color Scripter

cs

강사님은 입력과 출력에만 변화를 주면서,

최대힙으로 최소힙 효과를 낼 수 있도록 하셨다.

line 20) 입력에서 자연수에 - 를 붙이면서, 음수에서 대소비교를 하게 되므로

          작은 수가 위로 올라오게 된다.

line 16) 출력에서 다시 -을 붙여서 작은 수를 꺼내주었다.

굉장히 생각도 못한 신박한 방법이었다..

#. Result

  - Input --------------------------------------------------------

5 

3 

6 

0 

5 

0 

2 

4 

0 

-1

------------------------------------------------------------------

  - Output --------------------------------------------------------

3

5

2

------------------------------------------------------------------