[백준] 11279 최대 힙

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

https://github.com/sneakstarberry/

Abstract

[백준] 11279번 최대 힙

[백준] 11279번 최대 힙

백준 11279번

알고리즘 유형

풀이방법

굳이 이해할 것이 없어서 문제 이해 부분을 없앴다. 그냥 설명대로 풀면된다. 여기에 나는 map 자료구조를 이용하였는데 우선순위 큐가 알고리즘 유형으로 되어있길래 우선순위 큐가 코드짜기 쉬웠을 거라는 생각이 들었다.

#include <iostream>
#include <map>
#define endl '\n'
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, x;
  map<int, int> m;

  cin >> n;

  for (int i = 0; i < n; i++) {
    cin >> x;
    if (x == 0) {
      if (m.empty()) {
        cout << 0 << endl;
      } else {
        cout << -m.begin().operator*().first << endl;
        if (m.begin().operator*().second > 1) {
          m[m.begin().operator*().first]--;
        } else {
          m.erase(m.begin().operator*().first);
        }
      }
    } else {
      if (m[-x]) {
        m[-x]++;
      } else {
        m[-x] = 1;
      }
    }
  }

  return 0;
}

Originally published March 25, 2021
Latest update March 25, 2021

Related posts :

{# #}