[C++] 백준 11279 : 최대 힙
#include <iostream>
#include <queue> // 우선순위 큐를 이용하여 쉽게 힙을 구현할 수 있다.
using namespace std;
int N, x;
priority_queue<int> pq;
int main(int argc, char* argv[]){
scanf("%d",&N);
for(int i=0; i<N; i++){
scanf("%d",&x);
if(x == 0){ // 답 출력
if(!pq.empty()){
printf("%d\n", pq.top()); // front말고 top
pq.pop(); // 값 꺼내기
} else {
printf("0\n");
}
} else { // 힙에 값 넣기
pq.push(x);
}
}
return 0;
}
힙에 대해서 다시 공부해 볼 수 있는 시간이었다.
트리를 사용하여 높은 값을 트리의 부모 노드에 배치하는 그러한 완전 이진 트리의 형태를 띈다. 시험보면 무조건 나와서 아직 까먹지는 않았는데 트리를 직접 구현하라니 시간도 많이 들고 너무 막막했다...
그래서 인터넷을 조금 참고해서 문제를 풀었다.
바로 우선순위 큐를 활용하는 것이다. 우선순위 큐를 넣으면 자동으로 내림차순으로 정렬이 되기때문에 최대 힙처럼 사용이 가능하다는 것이다.
아니 어떻게 이런 생각을 하지? 사람들은 너무 똑똑해!
Author And Source
이 문제에 관하여([C++] 백준 11279 : 최대 힙), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lamknh/C-백준-11279-최대-힙저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)