썸네일 출처: https://ye-yo.github.io/thumbnail-maker/

📖 문제

1021번: 회전하는 큐

💡 아이디어

1. 큐에서 특정 위치의 값을 뽑아내는 방법

큐는 기본적으로 맨 앞에 있는 값만 뽑아낼 수 있으므로 중간에 있는 값을 뽑아내려면 큐를 시계방향 또는 반시계방향으로 회전시켜야 한다.(문제에서 각각 3번째, 2번째 연산에 해당함)

2. 필요한 회전량 구하기

맨 앞의 값을 뽑아서 맨 뒤에 푸쉬하는 연산, 즉 반시계방향 회전 연산에 필요한 횟수를 구하면 시계방향 회전 연산에 필요한 횟수는 (큐의 크기) - (반시계 연산 횟수)이다. 그러니 반시계 방향으로 회전시켰을 때 필요한 연산의 수만 구하면 된다.

3. 시계방향 회전과 반시계방향 회전의 결과는 같다

예를 들어 크기가 10인 큐에서 4번째 값을 뽑아내려고 한다면, 반시계방향으로 3번 회전시키거나 시계방향으로 7번 회전시켜야 한다. 이때 두 연산 이후 큐의 상태는 동일하므로 연산의 최소값을 구하려면 회전수가 작은 반시계방향으로 회전하는 것이 맞다.

✏️ 코드

use std::cmp::min;
use std::collections::VecDeque;
use std::io::{stdin, Read};

fn main() {
    let mut input = String::new();
    stdin().read_to_string(&mut input).unwrap();
    let mut input = input.split_ascii_whitespace().flat_map(str::parse::<i32>);
    let (n, m) = (input.next().unwrap(), input.next().unwrap());

    let mut move_count = 0;
    let mut deque: VecDeque<i32> = VecDeque::new();

    for i in 1..=n {
        deque.push_back(i);
    }

    for size in (n-m+1..=n).rev() {
        let index = input.next().unwrap();
        let mut left_move_count = 0;
        loop {
            let item = deque.pop_front().unwrap();
            if item == index {
                break;
            }
            deque.push_back(item);
            left_move_count += 1;
        }
        move_count += min(left_move_count, size - left_move_count);
    }

    println!("{move_count}");
}