73. 최대힙 [우선순위 큐 이용]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

5

3

6

0

5

0

2

4

0

-1

 

출력예제 1

6

5

5

 

풀이 

- 우선순위 큐를 이용한 최대힙 구조 만드는 문제

- 무조건 부모가 자식보다 큰 값을 가져야 한다

=> 우선순위 큐가 자식노드에 부모노드보다 큰 값이 들어오면 위치를 바꿔준다

- top을 출력하면 현재의 루트노드가 출력된다

 

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

//73. 최대힙 (우선순위 큐)
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(); //팝하면 루트 노드가 pop
            }
        }
        else pQ.push(a); //push하면 부모랑 비교해서 큰 게 위쪽 레벨로 올라감
    }
    return 0;
}