[Rust로 백준 하루 하나] 16-8. 요세푸스 문제 0

김진산·2024년 10월 16일

Rust로 백준 하루 하나

목록 보기

135/138

문제 (11866번)

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

풀이

코드

use std::io::{self, BufReader, BufRead, BufWriter, Write};

fn main() {
    let mut reader = BufReader::new(io::stdin().lock());
    let mut writer = BufWriter::new(io::stdout().lock());
    
    let mut input = String::new();
    reader.read_line(&mut input).unwrap();
    let mut input_iter = input
        .trim()
        .split_whitespace()
        .map(|i| i.parse::<usize>().unwrap());
    let n = input_iter.next().unwrap();
    let k = input_iter.next().unwrap();
    
    let mut people: Vec<bool> = vec![true; n];
    let mut index: usize = 0;
    write!(writer, "<").unwrap();
    loop {
        let mut count = k;
        while count != 0 {
            if people[index] == true { count -= 1; }
            if count != 0 { index += 1; }
            if index == n { index = 0; }
        }
        people[index] = false;
        write!(writer, "{}", index+1).unwrap();
        if people.iter().all(|&i| i == false) { break; }
        else { write!(writer, ", ").unwrap(); }
    }
    write!(writer, ">").unwrap();
}

해설

fn all<F>(&mut self, f: F) -> bool
where Self: Sized,
      F: FnMut(Self::Item) -> bool,

https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.all

추가 학습

큐를 쓰지 않고 저만의 방법을 생각해내서 풀었지만 큐를 사용하여 푸는 방법도 알아갑시다.

use std::io::{self, BufWriter, Write};

fn main() {
    let stdin = io::stdin();
    let mut writer = BufWriter::new(io::stdout());

    // 입력받기
    let mut input = String::new();
    stdin.read_line(&mut input).unwrap();
    let mut input = input.trim().split_whitespace();

    let n: usize = input.next().unwrap().parse().unwrap(); // N명의 사람
    let k: usize = input.next().unwrap().parse().unwrap(); // K번째 사람 제거

    let mut people: Vec<usize> = (1..=n).collect(); // 1번부터 N번까지 사람트
    let mut result = Vec::with_capacity(n); // 요세푸스 순열을 저장할 벡터

    let mut index = 0;

    // 사람들이 모두 제거될 때까지 반복
    while !people.is_empty() {
        // 제거할 사람의 위치 계산
        index = (index + k - 1) % people.len();
        // 사람 제거하고 결과에 추가
        result.push(people.remove(index));
    }

    // 요세푸스 순열 출력
    write!(writer, "<").unwrap();
    for (i, person) in result.iter().enumerate() {
        if i == result.len() - 1 {
            writeln!(writer, "{}", person).unwrap();
        } else {
            write!(writer, "{}, ", person).unwrap();
        }
    }
}