[백준] 11286 - 절댓값 힙

1. 문제

11286번: 절댓값 힙

2. 개요

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

N개의 연산이 주어진다. 연산 x가 0이 아닌 정수라면 이 값을 힙에 넣는 연산이고, 0이라면 힙에서 절댓값이 최소인 수를 뽑아내는 연산이다. 절댓값이 최소인 수가 여러개라면 값이 더 작은 수를 뽑고, 힙이 비어있다면 0을 출력한다.

3. 풀이 및 코드

3-1. 풀이

힙에 들어가는 수가 정수로 한정되고, 절댓값이 최소인 경우 더 작은 값을 우선 뽑아내야하므로 힙에 넣을 때 절댓값 + 차별화된 소수를 넣어 구별할 수 있다.

음수인 경우에는 0.1, 양수인 경우에는 0.2를 더해 다른 절댓값의 수와는 중복되지 않으면서 음, 양수를 구별할 수 있도록 한다.

뽑아낼 때는 힙을 이용하는 파이썬의 경우 맨 뒤의 숫자가 1이라면 음수인 경우이므로 -를 붙인 정수형으로 출력하고 아니라면 그대로 정수형으로 출력한다.

C#의 경우에는 값, 우선도 순으로 저장되기 때문에 항상 우선도가 높은 값을 뽑아내기만 하면 된다.

3-2. Python

import sys
import heapq

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

nums = []

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

    if num < 0:
        heapq.heappush(nums, abs(num) + 0.1)

    elif num > 0:
        heapq.heappush(nums, num + 0.2)

    else:
        if nums:
            k = heapq.heappop(nums)

            if str(k)[-1] == '1':
                print(-int(k))

            else:
                print(int(k))

        else:
            print(0)

3-3. C#

namespace boj_11286
{
    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, float> nums = new PriorityQueue<int, float>();

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

                if (num < 0)
                    nums.Enqueue(num, Math.Abs(num) + 0.1f);

                else if (num > 0)
                    nums.Enqueue(num, num + 0.2f);

                else
                {
                    if (nums.Count > 0)
                        sw.WriteLine(nums.Dequeue());

                    else
                        sw.WriteLine(0);
                }
            }

            sw.Close();
        }
    }
}