[C/C++] 백준 #1021 회전하는 큐

백준 문제 #1021 “회전하는 큐”는 덱(deque)을 활용하여 특정 위치에 있는 원소를 효율적으로 꺼내는 문제입니다. 문제의 목표는 주어진 순서대로 원하는 원소를 뽑아내기 위해 최소한의 연산 횟수를 계산하는 것입니다. 여기서 “연산”은 덱을 왼쪽으로 한 칸 회전하거나 오른쪽으로 한 칸 회전하는 작업, 혹은 첫 번째 원소를 직접 제거하는 작업을 의미합니다.

 

먼저, 입력으로는 N과 M이 주어지며, N은 큐에 포함된 원소의 총 개수를, M은 뽑아내고자 하는 원소의 개수를 나타냅니다. 이후 M개의 숫자가 주어지며, 이는 뽑아내야 할 원소의 위치를 나타냅니다. 큐는 처음에 1부터 N까지의 숫자가 순서대로 들어 있는 상태에서 시작합니다.

이 문제를 해결하려면 주어진 위치에 있는 원소를 뽑아내기 위해 큐를 최소한으로 회전시켜야 합니다. 이를 위해 각 원소를 꺼낼 때 두 가지 방향으로의 이동 횟수를 비교합니다. 왼쪽으로 회전하거나 오른쪽으로 회전하는 경우 중 더 작은 이동 횟수를 선택하여 총 연산 횟수를 누적합니다.

 

결과적으로, 문제는 덱을 사용하여 큐를 효율적으로 회전시키는 방법과 최적의 연산 경로를 선택하는 논리를 구현하는 것을 요구합니다. 이 과정에서 반복적으로 큐의 상태를 업데이트하며 최소 연산 횟수를 계산하는 것이 핵심입니다.

 

회전하는 큐 문제는 큐의 성질만 잘 이해하면 풀 수 있는 문제라고 보입니다.  정답률도 낮은 번호대 치고는 43%정도가 나와서 정답률이 높지는 않습니다.

3가지 연산이 가능한 회전하는 큐는, 1. 데이터 뽑아내기, 2. 왼쪽으로 한칸 회전, 3. 오른쪽으로 한칸 회전이 있습니다.

원하는 숫자 위치들을 뽑아낼 때, 2번과 3번의 동작을 최소한으로 하는 문제입니다. 얼듯보면 최적화 문제일 것같지만, 굳이 최적화 문제로 거론될 문제는 아닙니다.

 

문제의 링크는 다음과 같습니다.

https://www.acmicpc.net/problem/1021

 

현재 위치 c 와 뽑아내야할 데이터를 어느쪽으로 돌리면 빨리 갈 수 있는지만 검사하면 됩니다.

 

전 배열을 이용해서 구현했습니다.

최초 N개의 위치에 대한 배열을 0으로 초기화합니다. 그런후 데이터를 뽑을 때마다, 해당 배열 위치에 1로 기록을 합니다. 그런 후에 다음 숫자를 뽑을 때, 현재 위치와 비교하여 어느쪽이 빠른가를 검사합니다. 그 결과를 합산해서 보여주면 됩니다.

 

rotating queues

 

다음은 제가 작성한 소스입니다. 소스는 참고용으로만 봐주세요.

//----------------------------------------------------------
//    baekjoon #1021 - Rotating Queue
//        - by Aubrey Choi
//        - created at 2019-09-22
//----------------------------------------------------------
#include <stdio.h>

int main()
{
    int n, m, s, c=1, t, ans=0;
    static char v[52];
    scanf("%d%d",&n,&m);
    for(int r=0;r<m;r++)
    {
        scanf("%d",&s);
        for(t=0;c!=s;c=c%n+1) t+=v[c]==0;
        ans += (t<n-r-t)?t:n-r-t; v[c]=1;
    }
    printf("%d\n", ans);
}