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

문제 링크

1927번 - 최소 힙

설명

입력된 값을 자료구조에 저장하고, 요청이 있을 때 가장 작은 값을 꺼내는 문제입니다.

• 입력이 0이면 현재 저장된 값 중 가장 작은 값을 출력하고 제거합니다.
• 배열이 비어 있다면 0을 출력합니다.
• 0이 아닌 값이 들어오면 해당 값을 저장소에 추가합니다.

이러한 연산을 빠르게 처리하기 위해 최소 힙(우선순위 큐)을 사용합니다.

접근법

• 양의 정수가 주어지면 최소 힙에 값을 추가합니다.
• 입력이 0일 경우에는 다음과 같이 처리합니다:
  • 힙이 비어 있으면 0 출력
  • 비어 있지 않다면 가장 작은 값을 출력하고 제거
    

참고 : 최대 힙(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>();
    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;

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

  int cntOperator; cin >> cntOperator;
  priority_queue<int, vector<int>, greater<int>> pq;
  while (cntOperator--) {
    int num; cin >> num;
    if (num > 0) {
      pq.push(num);
    } else {
      if (pq.size() == 0) {
        cout << "0\n";
      } else {
        cout << pq.top() << "\n";
        pq.pop();
      }
    }
  }
  return 0;
}