[백준] 1927 최소 힙

March 27, 2021 ( last updated : March 27, 2021 )
우선순위 큐 자료구조 알고리즘 algorithm

https://github.com/sneakstarberry/

Abstract

[백준] 1927번 최소 힙

[백준] 1927번 최소 힙

백준 1927번

알고리즘 유형

풀이방법

굳이 이해할 것이 없어서 문제 이해 부분을 없앴다. 그냥 설명대로 풀면된다. 우선순위 큐로 풀었다. 우선순위 큐는 가장 큰수가 큐의 가장 위에 있기 때문에 -로 입력 값들의 부호를 바꾸어서 순서를 바꾸어 주었다. 역시 map말고 priority_queue로 푸니 훨씬 빨리 풀린다.

#include <iostream>
#include <queue>

#define endl '\n'

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  priority_queue<int> q;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int tmp;
    cin >> tmp;
    if (tmp == 0) {
      if (q.empty()) {
        cout << 0 << endl;
      } else {
        cout << -q.top() << endl;
        q.pop();
      }
    } else {
      q.push(-tmp);
    }
  }

  return 0;
}

Originally published March 27, 2021
Latest update March 27, 2021

Related posts :

{# #}