[백준] 11279 - 최대 힙

1. 문제

11279번: 최대 힙

2. 개요

최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

x가 자연수로 주어지면 연산 1을, 0으로 주어지면 연산 2, 0이고 배열이 빈 경우라면 0을 출력한다.

3. 풀이 및 코드

3-1. 풀이

파이썬의 heapq는 기본적으로 최소 힙이고, C#의 PriorityQueue는 Priority가 작은 순으로 정렬된다.

따라서 각각 파이썬에서는 heappush할 때 -1을 곱한 대소관계를 역전시킨 값을 넣고, 배열에서 빼내어 출력할 때 다시 -1을 곱한 값을 출력한다.

C#에서는 값은 그대로 넣고 Priority만 -1을 곱한 값을 넣어주면 된다.

3-2. Python

import sys
import heapq

N = int(sys.stdin.readline())

nums = []

for i in range(N):
    command = int(sys.stdin.readline())

    if command > 0:
        heapq.heappush(nums, -command)

    else:
        if nums:
            print(-heapq.heappop(nums))

        else:
            print(0)

3-3. C#

namespace boj_11279
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            int N = int.Parse(sr.ReadLine());

            PriorityQueue<int, int> nums = new PriorityQueue<int, int>();

            for (int i = 0; i < N; i++)
            {
                int commnad = int.Parse(sr.ReadLine());

                if (commnad > 0)
                    nums.Enqueue(commnad, -commnad);

                else if (nums.Count == 0)
                    sw.WriteLine(0);

                else
                    sw.WriteLine(nums.Dequeue());
            }

            sw.Close();
        }
    }
}