[백준] 2220번 : 힙 정렬

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

이 문제는 그리디하게 swap을 이용하여 해결하면 됩니다.

use io::Write;
use std::{io, str};

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 = scan.token::<usize>();
  let mut arr = vec![0; n + 1];

  arr[1] = 1;
  for i in 2..=n {
    arr[i] = i;

    arr.swap(i - 1, i);

    let mut j = i - 1;
    while j > 1 {
      arr.swap(j, j / 2);
      j /= 2;
    }
  }

  for i in 1..=n {
    write!(out, "{} ", arr[i]).unwrap();
  }
}