한가롭게 방학에 놀고 있던 도현이는 갑자기 재밌는 자료구조를 생각해냈다. 그 자료구조의 이름은 queuestack이다.

queuestack의 구조는 다음과 같다. 1번, 2번, ... , N번의 자료구조(queue 혹은 stack)가 나열되어있으며, 각각의 자료구조에는 한 개의 원소가 들어있다.

queuestack의 작동은 다음과 같다.

•  x_0을 입력받는다.
•  x_0을 1번 자료구조에 삽입한 뒤 1번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x1이라 한다.
•  x_1을 2번 자료구조에 삽입한 뒤 2번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x2이라 한다.
• ...
•  x_N−1을 N번 자료구조에 삽입한 뒤 N$N$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x_N이라 한다.
•  x_N을 리턴한다.

도현이는 길이 M의 수열 C를 가져와서 수열의 원소를 앞에서부터 차례대로 queuestack에 삽입할 것이다. 이전에 삽입한 결과는 남아 있다. (예제 1 참고)

queuestack에 넣을 원소들이 주어졌을 때, 해당 원소를 넣은 리턴값을 출력하는 프로그램을 작성해보자.

입력

첫째 줄에 queuestack을 구성하는 자료구조의 개수 N이 주어진다. (1≤N≤100000)

둘째 줄에 길이 N의 수열 A가 주어진다. i번 자료구조가 큐라면 A_i=0, 스택이라면 A_i=1이다.

셋째 줄에 길이 N의 수열 B가 주어진다. B_i는 i번 자료구조에 들어 있는 원소이다. (1≤B_i≤1000000000)

넷째 줄에 삽입할 수열의 길이 M이 주어진다. (1≤M≤100000)

다섯째 줄에 queuestack에 삽입할 원소를 담고 있는 길이 M의 수열 C가 주어진다. (1≤C_i≤1000000000)

입력으로 주어지는 모든 수는 정수이다.

출력

수열 C의 원소를 차례대로 queuestack에 삽입했을 때의 리턴값을 공백으로 구분하여 출력한다.

풀이

코드

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

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 n: usize = input.trim().parse().unwrap();

    input.clear();
    reader.read_line(&mut input).unwrap();
    let a: Vec<i32> = input
        .trim()
        .split_whitespace()
        .map(|i| i.parse().unwrap())
        .collect();

    input.clear();
    reader.read_line(&mut input).unwrap();
    let b: Vec<i32> = input
        .trim()
        .split_whitespace()
        .map(|i| i.parse().unwrap())
        .collect();

    input.clear();
    reader.read_line(&mut input).unwrap();
    let m: usize = input.trim().parse().unwrap();

    input.clear();
    reader.read_line(&mut input).unwrap();
    let c: Vec<i32> = input
        .trim()
        .split_whitespace()
        .map(|i| i.parse().unwrap())
        .collect();

    let mut queuestack: VecDeque<i32> = VecDeque::new();
    for (i, v) in b.iter().enumerate() {
        if a[i] == 0 { queuestack.push_back(b[i]); }
    }
    // println!("{:?}", queuestack);

    for i in c {
        queuestack.push_front(i);
        let output = queuestack.pop_back().unwrap();
        write!(writer, "{output} ").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 a = String::new();
    reader.read_line(&mut a).unwrap();
    let a: Vec<i32> = a
        .trim()
        .split_whitespace()
        .map(|i| i.parse().unwrap())
        .collect();

    let mut b = String::new();
    reader.read_line(&mut b).unwrap();
    let mut b: Vec<i32> = b
        .trim()
        .split_whitespace()
        .map(|i| i.parse().unwrap())
        .collect();

    let mut m = String::new();
    reader.read_line(&mut m).unwrap();
    let m: usize = m.trim().parse().unwrap();

    let mut c = String::new();
    reader.read_line(&mut c).unwrap();
    let c: Vec<i32> = c
        .trim()
        .split_whitespace()
        .map(|i| i.parse().unwrap())
        .collect();

    for i in 0..m {
        let mut output = c[i];
        for j in 0..n {
            if a[j] == 0 {
                let temp = output;
                output = b[j];
                b[j] = temp;
            }
        }
        write!(writer, "{output} ").unwrap();
    }
}

추가 학습

• 특이사항 없음

1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.

우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.

예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 종이에 0은 적혀있지 않다.

출력

첫째 줄에 터진 풍선의 번호를 차례로 나열한다.

풀이

코드

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();
    }
}

추가 학습

• 특이사항 없음

정수를 저장하는 덱을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

1. 1 X: 정수 X를 덱의 앞에 넣는다. (1 ≤ X ≤ 100,000)
2. 2 X: 정수 X를 덱의 뒤에 넣는다. (1 ≤ X ≤ 100,000)
3. 3: 덱에 정수가 있다면 맨 앞의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
4. 4: 덱에 정수가 있다면 맨 뒤의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
5. 5: 덱에 들어있는 정수의 개수를 출력한다.
6. 6: 덱이 비어있으면 1, 아니면 0을 출력한다.
7. 7: 덱에 정수가 있다면 맨 앞의 정수를 출력한다. 없다면 -1을 대신 출력한다.
8. 8: 덱에 정수가 있다면 맨 뒤의 정수를 출력한다. 없다면 -1을 대신 출력한다.

입력

첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄부터 N개 줄에 명령이 하나씩 주어진다.

출력을 요구하는 명령은 하나 이상 주어진다.

출력

출력을 요구하는 명령이 주어질 때마다 명령의 결과를 한 줄에 하나씩 출력한다.

풀이

코드

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

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 output: VecDeque<i32> = VecDeque::new();
    let mut input = String::new();
    for _ in 0..n {
        reader.read_line(&mut input).unwrap();
        let mut input_iter = input
            .trim()
            .split_whitespace();
        let inst = input_iter.next().unwrap();
        match inst {
            "1" => {
                let x = input_iter.next().unwrap().parse::<i32>().unwrap();
                output.push_front(x);
            },
            "2" => {
                let x = input_iter.next().unwrap().parse::<i32>().unwrap();
                output.push_back(x);
            },
            "3" => {
                if let Some(x) = output.pop_front() {
                    writeln!(writer, "{x}").unwrap();
                } else {
                    writeln!(writer, "-1").unwrap();
                }
            },
            "4" => {
                if let Some(x) = output.pop_back() {
                    writeln!(writer, "{x}").unwrap();
                } else {
                    writeln!(writer, "-1").unwrap();
                }
            },
            "5" => writeln!(writer, "{}", output.len()).unwrap(),
            "6" => {
                if output.len() == 0 {
                    writeln!(writer, "1").unwrap();
                } else {
                    writeln!(writer, "0").unwrap();
                }
            },
            "7" => {
                if output.len() != 0 {
                    writeln!(writer, "{}", output[0]).unwrap();
                } else {
                    writeln!(writer, "-1").unwrap();
                }
            },
            "8" => {
                if output.len() != 0 {
                    writeln!(writer, "{}", output[output.len()-1]).unwrap();
                } else {
                    writeln!(writer, "-1").unwrap();
                }
            },
            _ => (),
        }
        input.clear();
    }
}

해설

특이사항 없음

추가 학습

• 특이사항 없음

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

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();
        }
    }
}

이 코드는 chatGPT 코드이므로 그대로 복붙하면 틀릴 가능성이 있습니다. 그냥 보기에도 닫는 괄호가 없어서 틀릴 것 같습니다.

큐와 모듈러 연산, remove 메서드를 사용하여 문제를 해결한 방식을 보면 좋을 것 같습니다.

추가로 이 문제는 n과 k가 1000이하이기 때문에 괜찮지만 숫자가 커진다면 Linked List를 사용하는게 효율적이지 않을까 생각이 듭니다.

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

풀이

코드

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

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 cards: VecDeque<usize> = (1..=n).collect();
    while cards.len() != 1 {
        cards.pop_front().unwrap();
        let card = cards.pop_front().unwrap();
        cards.push_back(card);
    }
    writeln!(writer, "{}", cards[0]).unwrap();
}

해설

특이사항 없음

추가 학습

• 특이사항 없음

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이

코드

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

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 queue: VecDeque<i32> = VecDeque::new();
    let mut input = String::new();
    for _ in 0..n {
        reader.read_line(&mut input).unwrap();
        let mut line_iter = input.trim().split_whitespace();

        let inst = line_iter.next().unwrap();
        let mut output = 0;
        match inst {
            "push" => {
                let x: i32 = line_iter.next().unwrap().parse().unwrap();
                queue.push_back(x);
                input.clear();
                continue;
            },
            "pop" => {
                if queue.is_empty() { output = -1; }
                else {
                    output = queue.pop_front().unwrap();
                }
            },
            "size" => output = queue.len() as i32,
            "empty" => {
                if queue.is_empty() { output = 1; }
                else { output = 0; }
            },
            "front" => {
                if queue.is_empty() { output = -1; }
                else { output = queue[0] }
            },
            "back" => {
                if queue.is_empty() { output = -1; }
                else { output = queue[queue.len()-1] as i32; }
            },
            _ => ()
        }
        writeln!(writer, "{}", output).unwrap();
        input.clear();
    }
}

해설

처음엔 Vec을 가지고 풀어봤는데 시간초과를 만났습니다. 이유는 "pop"에서 맨 앞 요소를 제거할 때 사용한 remove가 요소를 제거할 때 나머지 요소를 전부 앞으로 이동시키기 때문에 시간 복잡도가 최악의 경우 O(n²)의 시간이 걸리기 때문입니다.

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 queue: Vec<i32> = Vec::new();
    let mut input = String::new();
    for _ in 0..n {
        reader.read_line(&mut input).unwrap();
        let mut line_iter = input.trim().split_whitespace();

        let inst = line_iter.next().unwrap();
        let mut output = 0;
        match inst {
            "push" => {
                let x: i32 = line_iter.next().unwrap().parse().unwrap();
                queue.push(x);
                input.clear();
                continue;
            },
            "pop" => {
                if queue.is_empty() { output = -1; }
                else {
                    output = queue.remove(0);
                }
            },
            "size" => output = queue.len() as i32,
            "empty" => {
                if queue.is_empty() { output = 1; }
                else { output = 0; }
            },
            "front" => {
                if queue.is_empty() { output = -1; }
                else { output = queue[0] }
            },
            "back" => {
                if queue.is_empty() { output = -1; }
                else { output = queue[queue.len()-1] as i32; }
            },
            _ => ()
        }
        writeln!(writer, "{}", output).unwrap();
        input.clear();
    }
}

따라서 러스트에서 큐를 구현할 때는 맨 앞에 추가/삭제 할 수 있는 메서드(push_front, pop_front)가 구현되어 있는 VecDeque를 사용해야 합니다.

추가 학습

• https://stackoverflow.com/questions/40848918/are-there-queue-and-stack-collections-in-rust
• https://doc.rust-lang.org/std/collections/struct.VecDeque.html

인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다. 

그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다. 다행히도 대기열의 왼쪽에는 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();
    }
}

추가 학습

• 특이사항 없음

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입력

각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

풀이

코드

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();
    loop {
        reader.read_line(&mut input).unwrap();
        input.pop();

        let mut stack: Vec<char> = Vec::new();
        if input == "." { break; }
        for c in input.chars() {
            match c {
                '[' => stack.push(c),
                '(' => stack.push(c),
                ']' => {
                    if stack.len() > 0 && stack[stack.len()-1] == '[' { stack.pop(); }
                    else { 
                        writeln!(writer, "no").unwrap();
                        break;
                    }
                },
                ')' => {
                    if stack.len() > 0 && stack[stack.len()-1] == '(' { stack.pop(); }
                    else { 
                        writeln!(writer, "no").unwrap();
                        break;
                    }
                },
                '.' => {
                    if stack.is_empty() {
                        writeln!(writer, "yes").unwrap();
                    } else {
                        writeln!(writer, "no").unwrap();
                    }
                },
                _ => (),

            }
        }
        input.clear();
    }
}

해설

처음에 문장이 끝나는 온점.에서 남은 괄호가 있는지 확인하는 코드를 작성하지 않아 틀렸는데 조심하도록 하자.

추가 학습

• 특이사항 없음

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.

풀이

코드

// 9012번, 괄호

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 t = String::new();
    reader.read_line(&mut t).unwrap();
    let t: usize = t.trim().parse().unwrap();
    let mut input = String::new();
    for _ in 0..t {
        let mut count = 0;
        reader.read_line(&mut input).unwrap();
        for c in input.chars() {
            match c {
                '(' => count += 1,
                ')' => count -= 1,
                _ => (),
            }
            if count < 0 { break; }
        }
        if count != 0 { writeln!(writer, "NO").unwrap(); }
        else { writeln!(writer, "YES").unwrap(); }
        input.clear();
    }
}

해설

다음엔 스택으로 풀어보도록 하자.

추가 학습

• 특이사항 없음

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

입력

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

출력

재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.

풀이

코드

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 k = String::new();
    reader.read_line(&mut k).unwrap();
    let k: usize = k.trim().parse().unwrap();

    let mut stack: Vec<u32> = Vec::new();
    let mut input = String::new();
    for _ in 0..k {
        reader.read_line(&mut input).unwrap();
        let n: u32 = input.trim().parse().unwrap();
        if n == 0 {
            stack.pop();
        } else {
            stack.push(n);
        }
        input.clear();
    }
    let output: u32 = stack.iter().sum();
    writeln!(writer, "{}", output).unwrap();
}

해설

특이사항 없음

추가 학습

• 특이사항 없음

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

1. 1 X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000)
2. 2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
3. 3: 스택에 들어있는 정수의 개수를 출력한다.
4. 4: 스택이 비어있으면 1, 아니면 0을 출력한다.
5. 5: 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다.

입력

첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄부터 N개 줄에 명령이 하나씩 주어진다.

출력을 요구하는 명령은 하나 이상 주어진다.

출력

출력을 요구하는 명령이 주어질 때마다 명령의 결과를 한 줄에 하나씩 출력한다.

풀이

코드

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 stack: Vec<i32> = Vec::new();
    let mut input = String::new();
    for _ in 0..n {
        reader.read_line(&mut input).unwrap();
        let mut input_iter = input
            .trim()
            .split_whitespace()
            .map(|i| i.parse::<i32>().unwrap());
        let inst = input_iter.next().unwrap();

        match inst {
            1 => {
                let x: i32 = input_iter.next().unwrap();
                stack.push(x);
            },
            2 => {
                if stack.len() == 0 {
                    writeln!(writer, "-1").unwrap();
                } else {
                    let output = stack.pop().unwrap();
                    writeln!(writer, "{output}").unwrap();
                }
            },
            3 => {
                writeln!(writer, "{}", stack.len()).unwrap();
            },
            4 => {
                if stack.len() == 0 { writeln!(writer, "1").unwrap(); }
                else { writeln!(writer, "0").unwrap(); }
            },
            5 => {
                if stack.len() == 0 {
                    writeln!(writer, "-1").unwrap();
                } else {
                    writeln!(writer, "{}", stack[stack.len()-1]).unwrap();
                }
            },
            _ => (),
        }
        input.clear();
    }
}

해설

match 구문에서 다음과 같이 러스트에게 명시적으로 앞의 갈래에 매칭되지 않은 어떠한 값도 사용하지 않을 것이며, 어떠한 코드도 실행하지 않기를 원한다고 알려줄 수 있습니다.

_ => ()

추가 학습

• 특이사항 없음

서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다.  2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.

예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,

1. 1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)
2. 2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)
3. 3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)

결과적으로 마지막에 열려 있는 창문의 개수는 1개 이다.

입력

첫 번째 줄에는 창문의 개수와 사람의 수 N(1 ≤ N ≤ 2,100,000,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 n = String::new();
    reader.read_line(&mut n).unwrap();
    let n: usize = n.trim().parse().unwrap();

    let count = (1..).take_while(|&x| x * x <= n).count();

    writeln!(writer, "{}", count).unwrap();
}

해설

처음엔 범위도 정해져있고 이전과 같이 에라토스테네스의 체로 풀면 되겠다하고 다음과 같이 풀었는데 메모리 초과 문제가 발생했다. 하지만 이 문제는 입력값 n이 21억까지 클 수 있기 때문에 다른 방법으로 풀어야한다.

이 문제는 사실 모든 창문에 대해 반복적으로 상태를 업데이트할 필요가 없습니다. 특정 창문이 마지막에 열려 있을 조건은 그 창문이 열리고 닫히는 횟수에 의해 결정됩니다. 구체적으로, 창문이 열리고 닫히는 횟수는 해당 창문의 번호의 약수 개수에 따라 결정됩니다. 이 때, 약수의 개수가 홀수인 경우 창문은 열려 있고, 짝수인 경우 창문은 닫혀 있습니다. 약수의 개수가 홀수일 때는 해당 번호가 완전 제곱수일 때에만 발생합니다.

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 windows = vec![false; n+1];
    for i in 1..=n {
        for j in (i..=n).step_by(i) {
            if windows[j] == true {
                windows[j] = false;
            } else {
                windows[j] = true;
            }
        }
    }

    let output = windows.iter().filter(|&&v| v == true).count();
    writeln!(writer, "{}", output).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 count = 0;
    for i in 1..=n {
        if square_number(i) { count += 1; }
    }

    writeln!(writer, "{}", count).unwrap();
}

fn square_number(n: usize) -> bool {
    let m = (n as f64).sqrt() as usize;
    if m * m == n { true }
    else { false }
}

추가 학습

fn take_while<P>(self, predicate: P) -> TakeWhile<Self, P>
where Self: Sized,
      P: FnMut(&Self::Item) -> bool,

• 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

출력

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

풀이

코드

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

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

    let mut t = String::new();
    reader.read_line(&mut t).unwrap();
    let t: usize = t.trim().parse().unwrap();

    // 에라토스테네스의 체로 미리 소수 구하기
    let max_n = 1_000_000;
    let is_prime = eratos(max_n);

    let mut input = String::new();
    for _ in 0..t {
        reader.read_line(&mut input).unwrap();
        let n: usize = input.trim().parse().unwrap();
        let mut count = 0;

        // 모든 가능한 소수쌍 찾기
        for i in 2..=n / 2 {
            if is_prime[i] && is_prime[n - i] {
                count += 1;
            }
        }

        writeln!(writer, "{}", count).unwrap();
        input.clear();
    }
}

// 에라토스테네스의 체를 사용해 소수 구하기
fn eratos(n: usize) -> Vec<bool> {
    let mut is_prime = vec![true; n + 1];
    is_prime[0] = false;
    is_prime[1] = false;

    for i in 2..=(n as f64).sqrt() as usize {
        if is_prime[i] {
            for j in (i * i..=n).step_by(i) {
                is_prime[j] = false;
            }
        }
    }

    is_prime
}

해설

특이사항 없음

추가 학습

• 특이사항 없음

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

풀이

코드

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

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

    let mut input = String::new();
    loop {
        reader.read_line(&mut input).unwrap();
        let n: u32 = input.trim().parse().unwrap();
        if n == 0 { break; }

        let mut count = 0;
        for i in n+1..=2*n {
            if is_prime(i) { count += 1; }
        }

        writeln!(writer, "{}", count).unwrap();
        input.clear();
    }
}

fn is_prime(i: u32) -> bool {
    if i < 2 { return false; }
    for div in 2..=(i as f64).sqrt() as u32 {
        if i % div == 0 { return false; }
    }
    true
}

해설

이 문제도 범위가 정해져 있으므로 다음에 에라토스테네스의 체를 사용하여 다시 풀어보자

추가 학습

• 특이사항 없음

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

풀이

코드

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

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::<u32>().unwrap());
    let m = input_iter.next().unwrap();
    let n = input_iter.next().unwrap();

    for i in m..=n {
        if is_prime(i) {
            writeln!(writer, "{}", i).unwrap();
        }
    }
}

fn is_prime(n: u32) -> bool {
    if n < 2 {
        false
    } else {
        for x in 2..=((n as f64).sqrt() as u32) {
            if n % x == 0 { return false; }
        }
        true
    }
}

해설

에라토스테네스의 체를 사용하여 풀어보려고 하였으나 시간이 너무 오래 걸려 제곱근까지 직접 나누는 방식으로 풀었습니다. 에라토스 테네스의 체로 푸는 방법은 추가 학습에서 다루겠습니다.

추가 학습

다음과 같이 에라토스테네스의 체를 구현할 수 있습니다.

let mut is_prime = vec![true; n + 1];
is_prime[0] = false;
is_prime[1] = false;

// 에라토스테네스의 체 구현
for i in 2..=((n as f64).sqrt() as usize) {
  if is_prime[i] {
    for j in (i * i..=n).step_by(i) {
      is_prime[j] = false;
    }
  }
}

참고로, step_by 메서드는 step 만큼 건너뛰는 함수입니다.

fn step_by(self, step: usize) -> StepBy<Self>
where Self: Sized,

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

정수 n($0 ≤ n ≤ 4*10^9$)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

출력

각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다.

풀이

코드

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

fn main() {
    let start_time = Instant::now();

    let mut reader = BufReader::new(io::stdin().lock());
    let mut writer = BufWriter::new(io::stdout().lock());

    let mut num = String::new();
    reader.read_line(&mut num).unwrap();
    let num: usize = num.trim().parse().unwrap();

    let mut input = String::new();
    for _ in 0..num {
        reader.read_line(&mut input).unwrap();
        let n: u32 = input.trim().parse().unwrap();

        // n보다 크거나 같은 소수 중 가장 작은 소수
        let mut output = n;
        'a: loop {
            let limit = (output as f64).sqrt() as u32;
            if output < 2 {
                output = 2;
            }
            for i in 2..=limit {
                if output % i == 0 {
                    output += 1;
                    continue 'a;
                }
            }
            break;
        }

        writeln!(writer, "{}", output).unwrap();
        input.clear();
    }

    let end_time = Instant::now();
    let elapsed_time = end_time.duration_since(start_time);
    println!("{:?}", elapsed_time);
}

해설

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 num = String::new();
    reader.read_line(&mut num).unwrap();
    let num: usize = num.trim().parse().unwrap();

    let mut input = String::new();
    for _ in 0..num {
        reader.read_line(&mut input).unwrap();
        let n: u32 = input.trim().parse().unwrap();

        // n보다 크거나 같은 소수 중 가장 작은 소수
        let mut output = n;
        'a: loop {
            for i in 2..=output/2 {
                if output % i == 0 { break; }
                else if i == output/2 { 
                    break 'a;
                }
            }
            output += 1;
        }

        writeln!(writer, "{}", output).unwrap();
        input.clear();
    }
}

처음엔 이렇게 나누기 2가 되는 수까지 반복을 했으나 시간초과가 나왔습니다. 지난번에 이렇게 풀어서 그대로 했던 건데 사실 제곱근까지만 반복하면 됩니다.

제곱근까지 반복하는 방식으로 해결할 수 있었지만 시간을 재보았을 때 3,4초 정도 나왔는데 문제의 시간제한 1초를 어떻게 통과했는지는 잘 모르겠습니다. 아시는 분은 댓글로 알려주시면 감사하겠습니다.

[!NOTE] Rust에서 as u32를 사용하여 소수점을 포함한 f64 값을 u32로 변환할 때, 소수점 이하 부분은 단순히 버려집니다 (즉, 내림 처리).

추가 학습

• 다양한 소수판별법 알고리즘
• 그 외 에라토스테네스의 체

직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.

편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.

예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.

심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.

입력

첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 1,000,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르고, N개의 가로수는 기준점으로부터 떨어진 거리가 가까운 순서대로 주어진다.

출력

모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.

풀이

코드

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();
    for _ in 0..n {
        reader.read_line(&mut input).unwrap();
    }
    let input: Vec<i32> = input
        .trim()
        .split_whitespace()
        .map(|i| i.parse().unwrap())
        .collect();

    // 가로수 간격 구하기
    let mut intervals: Vec<i32> = Vec::new();
    for i in 1..input.len() {
        intervals.push(input[i] - input[i-1]);
    }

    // 간격의 최대공약수 구하기
    let mut final_gcd: i32 = gcd(intervals[0], intervals[1]);
    for i in 2..intervals.len() {
        final_gcd = gcd(final_gcd, intervals[i]);
    }

    // 새로 심어야하는 개수 세기
    let output = (input[n-1] - input[0]) / final_gcd - (n as i32) + 1;
    writeln!(writer, "{}", output).unwrap();
}

fn gcd(mut a: i32, mut b: i32) -> i32 {
    while b != 0 {
        let r: i32 = a % b;
        a = b;
        b = r;
    }
    a
}

해설

특이사항 없음

추가 학습

• 특이사항 없음

분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자.

두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다.

입력

첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,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();
    for _ in 0..2 {
        reader.read_line(&mut input).unwrap();
    }
    let mut input_iter = input
        .trim()
        .split_whitespace()
        .map(|i| i.parse::<i32>().unwrap());
    let a_child = input_iter.next().unwrap();
    let a_parent = input_iter.next().unwrap();
    let b_child = input_iter.next().unwrap();
    let b_parent = input_iter.next().unwrap();

    // 분모의 최소공배수로 분수 더하기
    let parent = lcm(a_parent, b_parent);
    let child = a_child * (parent/a_parent) + b_child * (parent/b_parent);

    // 기약분수로 만들기
    let output_parent = parent / gcd(parent, child);
    let output_child = child / gcd(parent, child);

    writeln!(writer, "{} {}", output_child, output_parent).unwrap();
}

fn lcm(a: i32, b: i32) -> i32 {
    (a * b) / gcd(a, b)
}

fn gcd(mut a: i32, mut b: i32) -> i32 {
    let mut r: i32;
    while b != 0 {
        r = a % b;
        a = b;
        b = r;
    }
    a
}

해설

특이사항 없음

추가 학습

• 특이사항 없음

정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다.

예:

• 10은 5의 배수이다 (5*2 = 10)
• 10은 10의 배수이다(10*1 = 10)
• 6은 1의 배수이다(1*6 = 6)
• 20은 1, 2, 4,5,10,20의 배수이다.

다른 예:

• 2와 5의 최소공배수는 10이고, 그 이유는 2와 5보다 작은 공배수가 없기 때문이다.
• 10과 20의 최소공배수는 20이다.
• 5와 3의 최소공배수는 15이다.

당신은 두 수에 대하여 최소공배수를 구하는 프로그램을 작성 하는 것이 목표이다.

입력

한 줄에 두 정수 A와 B가 공백으로 분리되어 주어진다.

50%의 입력 중 A와 B는 1000(103)보다 작다. 다른 50%의 입력은 1000보다 크고 100000000(108)보다 작다.

추가: 큰 수 입력에 대하여 변수를 64비트 정수로 선언하시오. C/C++에서는 long long int를 사용하고, Java에서는 long을 사용하시오.

출력

A와 B의 최소공배수를 한 줄에 출력한다.

풀이

코드

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::<u64>().unwrap());
    let a = input_iter.next().unwrap();
    let b = input_iter.next().unwrap();
    let result = lcm(a, b);
    writeln!(writer, "{}", result).unwrap();
}

fn lcm(a: u64, b: u64) -> u64 {
    (a * b) / gcd(a, b)
}

fn gcd(mut a: u64, mut b: u64) -> u64 {
    let mut r: u64;
    while b != 0 {
        r = a % b;
        a = b;
        b = r;
    }
    a
}

해설

특이사항 없음

추가 학습

• 특이사항 없음

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

출력

첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

풀이

코드

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 t = String::new();
    reader.read_line(&mut t).unwrap();
    let t: usize = t.trim().parse().unwrap();

    for _ in 0..t {
        let mut input = String::new();
        reader.read_line(&mut input).unwrap();
        let mut input_iter = input
            .trim()
            .split_whitespace()
            .map(|i| i.parse::<u32>().unwrap());
        let a = input_iter.next().unwrap();
        let b = input_iter.next().unwrap();

        let result = lcm(a, b);
        writeln!(writer, "{}", result).unwrap();
    }
}

fn lcm(a: u32, b: u32) -> u32 {
    (a * b) / gcd(a, b)
}

fn gcd(mut a: u32, mut b: u32) -> u32 {
    let mut r: u32;
    while b != 0 {
        r = a % b;
        a = b;
        b = r;
    }
    a
}

해설

최대공약수, 최소공배수 구하는 방법 맨날 까먹는데 잘 기억해두자

추가 학습

• 특이사항 없음