[백준 11279] 최대 힙 (C#, C++) - soo:bak

문제 링크

11279번 - 최대 힙

설명

정수를 배열에 넣고, 가장 큰 값을 출력하거나 삭제하는 연산을 빠르게 처리하는 자료구조를 구현하는 문제입니다.

입력으로는 연산의 개수 n이 주어지고, 이후 n개의 줄에 숫자가 주어집니다.

• 입력이 0이면 현재 배열에서 가장 큰 값을 출력하고 제거합니다.
• 배열이 비어 있다면 0을 출력합니다.
• 입력이 0이 아니라면 배열에 해당 값을 추가합니다.

가장 큰 값을 빠르게 꺼낼 수 있어야 하므로, 최대 힙(우선순위 큐)을 사용합니다.

접근법

• 입력이 양수이면 우선순위 큐에 값을 추가합니다.
• 입력이 0이면 큐가 비었는지 확인하고:
  • 비어 있으면 0을 출력
  • 아니라면 최댓값을 출력하고 제거

우선순위 큐의 삽입과 삭제는 모두 \(O(\log N)\)의 시간복잡도를 가집니다.

참고 : 최대 힙(Max Heap)과 우선순위 큐의 원리와 구현 - soo:bak

언어 별 다음과 같은 차이점에 주의합니다 :

• C++ : 기본 최대 힙, 큰 값 우선. 최소 힙은 추가 설정 필요.
• C# : 기본 최소 힙, 작은 값 우선. 최대 힙은 비교자 지정 필요.

Code

C#

using System;
using System.Collections.Generic;
using System.Text;

class Program {
  static void Main() {
    int n = int.Parse(Console.ReadLine());
    var pq = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
    var sb = new StringBuilder();

    for (int i = 0; i < n; i++) {
      int x = int.Parse(Console.ReadLine());
      if (x > 0) pq.Enqueue(x, x);
      else sb.AppendLine(pq.Count == 0 ? "0" : pq.Dequeue().ToString());
    }

    Console.Write(sb.ToString());
  }
}

C++

#include <bits/stdc++.h>

using namespace std;
typedef priority_queue<int> pqi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  pqi pq;
  while (n--) {
    int x; cin >> x;
    if (x > 0) pq.push(x);
    else {
      if (pq.empty()) cout << "0\n";
      else {
        cout << pq.top() << "\n";
        pq.pop();
      }
    }
  }

  return 0;
}