우선순위 큐 인터페이스와, 비교 방법을 받아 그 인터페이스를 구현하는 제네릭 이진 힙 클래스를 직접 만들어라. 언어에 들어 있는 우선순위 큐는 쓰지 않는다.
그 힙 클래스 하나로 작업 대기열과, 우선순위의 중앙값을 구하는 정수 힙 두 개를 모두 만든다.
첫 줄에 명령 수 n이, 다음 n줄에 명령이 하나씩 주어진다.
"add name p"는 이름이 name이고 우선순위가 p인 작업을 대기열에 넣는다. 같은 이름이 여러 번 나올 수 있고, 서로 다른 작업으로 친다.
"next"는 대기열에서 우선순위가 가장 큰 작업을 꺼내 "name p"로 출력한다. 우선순위가 같으면 먼저 넣은 작업을 꺼낸다. 대기열이 비었으면 -를 출력한다.
"median"은 지금까지 add로 넣은 모든 우선순위의 중앙값을 출력한다. 이미 꺼낸 작업의 우선순위도 셈에 넣는다.
넣은 우선순위가 짝수 개면 가운데 두 값 가운데 작은 것을 출력한다. 아직 넣은 것이 없으면 -를 출력한다.
입력
1 ≤ n ≤ 100,000. name은 영어 소문자 1 ~ 10글자. -2,000,000,000 ≤ p ≤ 2,000,000,000(정수). next와 median은 합쳐서 5,000개 이하다.
출력
next와 median마다 한 줄
예시 1 · stdin
9
add wash 3
add cook 5
add read 5
median
next
next
add nap -2
median
next
stdout
5
cook 5
read 5
3
wash 3
예시 2 · stdin
6
next
median
add big 2000000000
add low -2000000000
next
median
stdout
-
-
big 2000000000
-2000000000
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 3개 언어 풀이
이 문제는 인터페이스와 제네릭이 있는 TypeScript·Java·C#만 받아요(JS에는 인터페이스도 타입 매개변수도 없고, Python은 Protocol과 타입 매개변수를 적을 수는 있어도 실행할 때 검사하지 않아요. C와 크레이콘에는 둘 다 없고, C++ 템플릿은 모양이 많이 달라서 뺐어요). 힙 클래스 하나를 T와 비교 방법만 바꿔 작업(Task)에도 정수에도 써요. 비교 방법은 Java Comparator<? super T>, C# Comparison<T>, TS (a: T, b: T) => boolean 같은 함수 타입으로 받아요. Java는 BinaryHeap<int>를 못 써서 Integer로 담고, C# 제네릭은 int를 포장 없이 담아요. 언어에 들어 있는 우선순위 큐도 서로 달라요. Java java.util.PriorityQueue와 C# PriorityQueue<TElement, TPriority>(.NET 6)는 가장 작은 것이 먼저 나오고, TS(JavaScript)에는 아예 없어요. Java 큐를 for-each로 돌거나 출력하면 힙 배열 순서라서 정렬돼 있지 않아요. 함정 셋: ① 비교를 b - a처럼 빼기로 하면 Java·C#의 int에서 20억 − (−20억)이 넘쳐 부호가 뒤집혀요. Integer.compare·CompareTo를 써요(TS의 수는 실수라 넘치지 않아요). ② 힙은 같은 것끼리 넣은 차례를 지키지 않아요. 두 언어의 내장 큐도 같은 우선순위의 차례를 약속하지 않아서, C# 내장 큐에 우선순위만 주면 같은 우선순위의 작업이 섞여 나와요. 넣은 차례를 비교에 함께 넣어야 해요. ③ TS 엄격 모드에서 pop()의 반환 타입은 T | undefined라 확인해야 쓸 수 있어요. !로 검사를 끄면 컴파일은 되지만 빈 큐에서 TypeError가 나요(Java 풀이는 null, C# 풀이는 TryPop의 false로 알려요). 중앙값은 작은 절반을 가장 큰 것이 위인 힙에, 큰 절반을 가장 작은 것이 위인 힙에 나눠 담고, 작은 절반 쪽이 하나 더 많거나 같게 맞추면 그 힙의 맨 위가 답이에요.
TypeScriptmain.ts · 87 줄
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); }}