[Rust로 백준 하루 하나] 16-6. 큐 2

문제 (18258번)

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

 

명령은 총 여섯 가지이다.

 

• 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