알고리즘/백준

백준 11279 최대 힙 c++ [컴공과고씨]

시간빌게이츠 2022. 4. 3. 16:01
반응형

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

 

11279번: 최대 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가

www.acmicpc.net

priority queue 우선순위 큐를 사용하면 쉽게 풀리는 문제이다.

priority queue를 간단히 설명하자면 heap으로 구성된 queue로 항상 최대값 혹은 최소값이 root에 있다.

priority_queue는 default로는 최소값이 root에 있기 때문에 이것을 그대로 사용해주면 된다.

 

 

전체코드

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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    vector<int> result;
    int n, x;
    cin >> n;
 
    priority_queue<int> q;
    for (int i = 0; i < n; i++){
        cin >> x;
        if(x!=0){
            q.push(x);
        }else{
            if(q.empty()){
                result.push_back(0);
            }else{
                result.push_back(q.top());
                q.pop();
            }
        }
    }
    for (int i = 0; i < result.size(); i++){
        cout << result[i] << '\n';
    }
        return 0;
}
cs

 

반응형