[백준 11286] 절댓값 힙 (C#, C++) - soo:bak

문제 링크

11286번 - 절댓값 힙

설명

절댓값 기준으로 우선순위를 정하여 수를 삽입 및 제거하는 힙 구조를 구현하는 문제입니다.

• 0이 아닌 정수는 우선순위 큐에 삽입합니다.
• 0이 입력되면, 현재 큐에서 절댓값이 가장 작은 수를 출력하고 제거합니다.
• 절댓값이 같은 경우에는 값이 작은 수를 먼저 출력해야 합니다.
• 큐가 비어 있는데 0이 입력된 경우에는 0을 출력합니다.

접근법

문제 해결을 위해 입력으로 주어지는 수들을 하나씩 처리하면서,

절댓값이 가장 작은 값을 빠르게 꺼낼 수 있어야 합니다.

이를 위해 절댓값 기준으로 정렬되는 우선순위 큐를 사용하며,

단순히 크기 비교만으로는 원하는 순서를 보장할 수 없기 때문에 비교 방식 자체를 직접 정의해줘야 합니다.

• 두 수의 절댓값이 다르면, 절댓값이 더 작은 수가 먼저 나와야 하고
• 절댓값이 같다면, 음수인 수가 양수보다 먼저 나와야 합니다

이 정렬 기준을 우선순위 큐에 적용하면, 각 숫자가 들어올 때마다 조건에 맞는 순서로 정렬할 수 있습니다.

0이 입력될 때는 그 기준에 따라 큐의 최상단 값을 출력하고 제거합니다.

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

---

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 abs, int val)>();
    var sb = new StringBuilder();

    while (n-- > 0) {
      int x = int.Parse(Console.ReadLine());
      if (x != 0) pq.Enqueue(x, (Math.Abs(x), x));
      else sb.AppendLine(pq.Count > 0 ? pq.Dequeue().ToString() : "0");
    }

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

C++

#include <bits/stdc++.h>

using namespace std;
typedef vector<int> vi;

struct cmp {
  bool operator()(int a, int b) {
    return abs(a) == abs(b) ? a > b : abs(a) > abs(b);
  }
};

typedef priority_queue<int, vi, cmp> pq_t;

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

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

  return 0;
}