[백준] 11920번 : 버블 정렬

https://www.acmicpc.net/problem/11920

해당 문제는 n개의 수를 입력받으면서 k번째 수부터 우선순위큐에서 제거하여 출력하는 방식으로 해결할 수 있습니다.

Rust에서의 heap은 최대힙이므로 Reverse()를 활용하여 최소힙으로 구성하여 해결하면 됩니다.

use io::Write;
use std::{io, str};
use std::cmp::Reverse;
use std::collections::BinaryHeap;

pub struct UnsafeScanner<R> {
  reader: R,
  buf_str: Vec<u8>,
  buf_iter: str::SplitAsciiWhitespace<'static>,
}

impl<R: io::BufRead> UnsafeScanner<R> {
  pub fn new(reader: R) -> Self {
    Self {
      reader,
      buf_str: vec![],
      buf_iter: "".split_ascii_whitespace(),
    }
  }

  pub fn token<T: str::FromStr>(&mut self) -> T {
    loop {
      if let Some(token) = self.buf_iter.next() {
        return token.parse().ok().expect("Failed parse");
      }
      self.buf_str.clear();
      self.reader
          .read_until(b'\n', &mut self.buf_str)
          .expect("Failed read");
      self.buf_iter = unsafe {
        let slice = str::from_utf8_unchecked(&self.buf_str);
        std::mem::transmute(slice.split_ascii_whitespace())
      }
    }
  }

  pub fn token_eof<T: str::FromStr>(&mut self) -> Option<T> {
    loop {
      if let Some(token) = self.buf_iter.next() {
        return token.parse().ok();
      }
      self.buf_str.clear();
      if self.reader.read_until(b'\n', &mut self.buf_str).unwrap() == 0 {
        return None;
      }
      self.buf_iter = unsafe {
        let slice = str::from_utf8_unchecked(&self.buf_str);
        std::mem::transmute(slice.split_ascii_whitespace())
      }
    }
  }

  pub fn line(&mut self) -> String {
    let mut input = String::new();
    self.reader.read_line(&mut input).expect("Failed read");
    input
  }
}

fn main() {
  let (stdin, stdout) = (io::stdin(), io::stdout());
  let mut scan = UnsafeScanner::new(stdin.lock());
  let mut out = io::BufWriter::new(stdout.lock());

  let (n, k) = (scan.token::<usize>(), scan.token::<usize>());
  let mut pq = BinaryHeap::new();

  for i in 0..n {
    pq.push(Reverse(scan.token::<i64>()));

    if i >= k {
      write!(out, "{} ", pq.pop().unwrap().0).unwrap();
    }
  }

  while !pq.is_empty() {
    write!(out, "{} ", pq.pop().unwrap().0).unwrap();
  }
}