백준 알고리즘
[Silver V] 요세푸스 문제 0 - 11866
성능 요약
메모리: 13156 KB, 시간: 4 ms
분류
자료 구조, 구현, 큐
문제 설명
요세푸스 문제는 다음과 같다.
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)
출력
예제와 같이 요세푸스 순열을 출력한다.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
use std::collections::VecDeque;
use std::io::{stdin, BufRead, BufReader, BufWriter, Write,stdout};
fn main() {
let mut people: VecDeque<usize> = VecDeque::new();
let mut removed_people_num = 0;
let mut current = 1;
let stdin = stdin();
let mut reader = BufReader::new(stdin.lock());
let mut buffer = String::new();
reader.read_line(&mut buffer).unwrap();
let mut nums = buffer.trim().split_whitespace().map(|x| x.parse::<usize>().unwrap());
let n = nums.next().unwrap();
let k = nums.next().unwrap();
for i in 1..=n {
people.push_back(i);
}
print!("<");
while let Some(front) = people.pop_front() {
if current % k == 0 {
print!("{}", front);
removed_people_num += 1;
if removed_people_num != n {
print!(", ");
}
} else {
people.push_back(front);
}
current += 1;
}
println!(">");
stdout().flush().expect("Failed to flush stdout");
}
