import { readFileSync } from "node:fs";// 우선순위 큐의 약속: 어떤 T든, "먼저 나올 것"을 정하는 비교 함수만 있으면 된다interface PriorityQueue<T> { push(item: T): void; pop(): T | undefined; // 비었으면 undefined peek(): T | undefined; size(): number;}// 이진 힙: before(a, b)가 참이면 a가 b보다 먼저 나온다class BinaryHeap<T> implements PriorityQueue<T> { private items: T[] = []; constructor(private before: (a: T, b: T) => boolean) {} push(item: T): void { const a = this.items; a.push(item); let i = a.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (!this.before(a[i], a[parent])) break; [a[i], a[parent]] = [a[parent], a[i]]; i = parent; } } pop(): T | undefined { const a = this.items; if (a.length === 0) return undefined; const top = a[0]; const last = a.pop() as T; if (a.length > 0) { a[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let best = i; if (l < a.length && this.before(a[l], a[best])) best = l; if (r < a.length && this.before(a[r], a[best])) best = r; if (best === i) break; [a[i], a[best]] = [a[best], a[i]]; i = best; } } return top; } peek(): T | undefined { return this.items[0]; } size(): number { return this.items.length; }}interface Task { name: string; priority: number; order: number; // 넣은 차례: 우선순위가 같으면 먼저 넣은 것부터}// 같은 BinaryHeap을 T = Task, T = number로 쓴다const tasks = new BinaryHeap<Task>((a, b) => a.priority !== b.priority ? a.priority > b.priority : a.order < b.order);const low = new BinaryHeap<number>((a, b) => a > b); // 작은 절반, 가장 큰 것이 위const high = new BinaryHeap<number>((a, b) => a < b); // 큰 절반, 가장 작은 것이 위function addPriority(p: number): void { low.push(p); high.push(low.pop() as number); // 작은 절반의 가장 큰 것을 큰 절반으로 if (high.size() > low.size()) low.push(high.pop() as number);}const lines: string[] = readFileSync(0, "utf8").split("\n");const n: number = Number(lines[0]);const out: string[] = [];for (let i = 1; i <= n; i++) { const [op, name, p] = lines[i].trim().split(" "); if (op === "add") { tasks.push({ name, priority: Number(p), order: i }); addPriority(Number(p)); } else if (op === "next") { const t = tasks.pop(); out.push(t === undefined ? "-" : `${t.name} ${t.priority}`); } else { const m = low.peek(); out.push(m === undefined ? "-" : String(m)); }}console.log(out.join("\n"));
JavaMain.java · 102 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Comparator;import java.util.List;// 우선순위 큐의 약속: 어떤 T든, 비교 방법(Comparator)만 있으면 된다interface PriorityQueue<T> { void push(T item); T pop(); // 비었으면 null T peek(); // 비었으면 null int size();}// 이진 힙: order.compare(a, b) < 0 이면 a가 b보다 먼저 나온다class BinaryHeap<T> implements PriorityQueue<T> { private final List<T> items = new ArrayList<>(); private final Comparator<? super T> order; BinaryHeap(Comparator<? super T> order) { this.order = order; } private boolean before(int i, int j) { return order.compare(items.get(i), items.get(j)) < 0; } private void swap(int i, int j) { T tmp = items.get(i); items.set(i, items.get(j)); items.set(j, tmp); } public void push(T item) { items.add(item); int i = items.size() - 1; while (i > 0 && before(i, (i - 1) / 2)) { swap(i, (i - 1) / 2); i = (i - 1) / 2; } } public T pop() { if (items.isEmpty()) return null; T top = items.get(0); T last = items.remove(items.size() - 1); if (!items.isEmpty()) { items.set(0, last); int i = 0; while (true) { int l = 2 * i + 1, r = l + 1, best = i; if (l < items.size() && before(l, best)) best = l; if (r < items.size() && before(r, best)) best = r; if (best == i) break; swap(i, best); i = best; } } return top; } public T peek() { return items.isEmpty() ? null : items.get(0); } public int size() { return items.size(); }}record Task(String name, int priority, int order) {}public class Main { // 같은 BinaryHeap을 T = Task, T = Integer로 쓴다(List<int>처럼 int는 못 넣는다) static final PriorityQueue<Task> tasks = new BinaryHeap<>( Comparator.comparingInt(Task::priority).reversed().thenComparingInt(Task::order)); static final PriorityQueue<Integer> low = new BinaryHeap<>(Comparator.reverseOrder()); // 작은 절반, 가장 큰 것이 위 static final PriorityQueue<Integer> high = new BinaryHeap<>(Comparator.naturalOrder()); // 큰 절반, 가장 작은 것이 위 static void addPriority(int p) { low.push(p); high.push(low.pop()); // 작은 절반의 가장 큰 것을 큰 절반으로 if (high.size() > low.size()) low.push(high.pop()); } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int i = 1; i <= n; i++) { String[] p = in.readLine().trim().split(" "); switch (p[0]) { case "add" -> { int pri = Integer.parseInt(p[2]); tasks.push(new Task(p[1], pri, i)); addPriority(pri); } case "next" -> { Task t = tasks.pop(); out.append(t == null ? "-" : t.name() + " " + t.priority()).append('\n'); } default -> { Integer m = low.peek(); out.append(m == null ? "-" : m.toString()).append('\n'); } } } System.out.print(out); }}
C#Main.cs · 103 行
using System;using System.Collections.Generic;using System.Text;// 우선순위 큐의 약속: 어떤 T든, 비교 방법(Comparison<T>)만 있으면 된다interface IPriorityQueue<T>{ void Push(T item); bool TryPop(out T item); // 비었으면 false bool TryPeek(out T item); int Count { get; }}// 이진 힙: order(a, b) < 0 이면 a가 b보다 먼저 나온다class BinaryHeap<T> : IPriorityQueue<T>{ private readonly List<T> items = new(); private readonly Comparison<T> order; public BinaryHeap(Comparison<T> order) { this.order = order; } private bool Before(int i, int j) => order(items[i], items[j]) < 0; private void Swap(int i, int j) => (items[i], items[j]) = (items[j], items[i]); public void Push(T item) { items.Add(item); int i = items.Count - 1; while (i > 0 && Before(i, (i - 1) / 2)) { Swap(i, (i - 1) / 2); i = (i - 1) / 2; } } public bool TryPop(out T item) { if (items.Count == 0) { item = default!; return false; } item = items[0]; items[0] = items[^1]; items.RemoveAt(items.Count - 1); int i = 0; while (true) { int l = 2 * i + 1, r = l + 1, best = i; if (l < items.Count && Before(l, best)) best = l; if (r < items.Count && Before(r, best)) best = r; if (best == i) break; Swap(i, best); i = best; } return true; } public bool TryPeek(out T item) { item = items.Count > 0 ? items[0] : default!; return items.Count > 0; } public int Count => items.Count;}record Task(string Name, int Priority, int Order);class Program{ // 같은 BinaryHeap을 T = Task, T = int로 쓴다(C# 제네릭은 int를 포장 없이 담는다) static readonly IPriorityQueue<Task> tasks = new BinaryHeap<Task>((a, b) => a.Priority != b.Priority ? b.Priority.CompareTo(a.Priority) : a.Order.CompareTo(b.Order)); static readonly IPriorityQueue<int> low = new BinaryHeap<int>((a, b) => b.CompareTo(a)); // 작은 절반, 가장 큰 것이 위 static readonly IPriorityQueue<int> high = new BinaryHeap<int>((a, b) => a.CompareTo(b)); // 큰 절반, 가장 작은 것이 위 static void AddPriority(int p) { low.Push(p); low.TryPop(out int top); high.Push(top); // 작은 절반의 가장 큰 것을 큰 절반으로 if (high.Count > low.Count && high.TryPop(out int small)) low.Push(small); } static void Main() { int n = int.Parse(Console.ReadLine()!.Trim()); var output = new StringBuilder(); for (int i = 1; i <= n; i++) { string[] p = Console.ReadLine()!.Trim().Split(' '); if (p[0] == "add") { int pri = int.Parse(p[2]); tasks.Push(new Task(p[1], pri, i)); AddPriority(pri); } else if (p[0] == "next") output.Append(tasks.TryPop(out var t) ? $"{t.Name} {t.Priority}" : "-").Append('\n'); else output.Append(low.TryPeek(out int m) ? m.ToString() : "-").Append('\n'); } Console.Write(output); }}