[Rust로 백준 하루 하나] 16-5. 도키도키 간식드리미
문제 (12789번)
인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다.
그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다. 다행히도 대기열의 왼쪽에는 1열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모른다. 자칫 간식을 못 받게 될지도 모른다는 위기감을 느낀 승환이는 자신의 컴퓨터 알고리즘적 지식을 활용해 과연 모든 사람들이 순서대로 간식을 받을 수 있는지 확인하는 프로그램을 만들기로 했다. 만약 불가능 하다면 승환이는 이번 중간고사를 망치게 될 것 이고 가능하다면 힘을 얻어 중간고사를 잘 볼 수 있을지도 모른다.
사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다. 인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다. 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다. 현재 대기열의 사람들은 이 공간으로 올 수 있지만 반대는 불가능하다. 승환이를 도와 프로그램을 완성하라.
현재 간식 배부 공간을 그림으로 나타내면 다음과 같다.
위 예제는 다음 그림과 같이 움직였을 때 모두가 순서대로 간식을 받을 수 있다..
입력
입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다.
다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,...,N) 순서가 앞에서부터 뒤 순서로 주어진다.
출력
승환이가 무사히 간식을 받을 수 있으면 "Nice"(따옴표는 제외)를 출력하고 그렇지 않다면 "Sad"(따옴표는 제외)를 출력한다.
풀이
코드
use std::collections::VecDeque;
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 n = String::new();
reader.read_line(&mut n).unwrap();
let n: usize = n.trim().parse().unwrap();
let mut input = String::new();
reader.read_line(&mut input).unwrap();
let balloons: Vec<i32> = input
.trim()
.split_whitespace()
.map(|i| i.parse().unwrap())
.collect();
// 풍선 번호와 이동 값을 저장하는 VecDeque
let mut queue: VecDeque<(usize, i32)> = VecDeque::new();
for i in 0..n {
queue.push_back((i + 1, balloons[i])); // (풍선 번호, 종이에 적힌 값)
}
// 첫 번째 풍선을 터뜨리고 시작
let mut result = Vec::new();
let mut current = queue.pop_front().unwrap();
result.push(current.0);
while !queue.is_empty() {
let steps = current.1;
if steps > 0 {
// 오른쪽으로 이동 (steps-1만큼 이동)
for _ in 0..(steps - 1) {
let front = queue.pop_front().unwrap();
queue.push_back(front);
}
} else {
// 왼쪽으로 이동 (steps만큼 이동)
for _ in 0..(-steps) {
let back = queue.pop_back().unwrap();
queue.push_front(back);
}
}
// 다음 터뜨릴 풍선 선택
current = queue.pop_front().unwrap();
result.push(current.0);
}
// 결과 출력
writeln!(writer, "{}", result.iter().map(|x| x.to_string()).collect::<Vec<_>>().join(" ")).unwrap();
}
해설
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 n = String::new();
reader.read_line(&mut n).unwrap();
let n: usize = n.trim().parse().unwrap();
let mut input = String::new();
reader.read_line(&mut input).unwrap();
let input: Vec<i32> = input
.trim()
.split_whitespace()
.map(|i| i.parse().unwrap())
.collect();
let mut visited: Vec<bool> = vec![false; n];
let mut pointer: usize = 0;
write!(writer, "{}", pointer + 1).unwrap();
for _ in 1..n {
let mut counter = input[pointer];
visited[pointer] = true;
while counter != 0 {
if counter < 0 {
counter += 1;
pointer -= 1;
if pointer == 0 { pointer += n-1; }
while visited[pointer] == true { pointer -= 1; }
} else {
counter -= 1;
pointer += 1;
if pointer == n-1 { pointer -= n-1; }
while visited[pointer] == true { pointer -= 1; }
}
}
write!(writer, " {}", pointer + 1).unwrap();
}
}추가 학습
- 특이사항 없음