백준 1021번 문제 - 회전하는 큐

---

문제 링크 : https://www.acmicpc.net/problem/1021

회전하는 큐 문제는 다음과 같은 3가지 연산을 수행한다.

1. 첫 번째 원소를 뽑아낸다.
2. 원소들을 좌측으로 한 칸씩 이동시킨다.
3. 원소들을 우측으로 한 칸씩 이동시킨다.

2번 연산 이후 3번 연산을 사용하게 된다면 원소는 제자리로 돌아가게 될 것이다.

따라서 원소를 뽑아내는데 필요한 2, 3번 연산의 최소 값은 원하는 원소가 첫 번째 원소가 될 때 까지 2번 연산을 수행하거나 3번 연산을 수행하는 경우 중 수행한 연산의 최소 값이 된다.

(원소의 위치)와 (원소의 위치 - 큐의 크기)의 계산으로 이를 확인하였으며 구현한 내용은 아래와 같다.

#include<iostream>
#include<vector>
using namespace std;
int N,M,result=0;
vector<int> vec;

void myPop(int k){
    int current = 0;
    while(vec[current]!=k)        current++;    //뽑아내고자 하는 원소의 위치 확인
    if(current<vec.size()-current){//2번 연산
        while(vec.front()!=k){
            vec.push_back(vec.front());
            vec.erase(vec.begin());
            result++;
        }
    }else{//3번 연산
        while(vec.front()!=k){
            vec.insert(vec.begin(),vec.back());
            vec.pop_back();
            result++;
        }
    }
    vec.erase(vec.begin());//1번 연산
}

int main(){
    scanf("%d %d",&N,&M);
    for(int i=1;i<=N;i++){
        vec.push_back(i);
    }
    for(int i=0;i<M;i++){
        int k;
        scanf("%d",&k);
        myPop(k);
    }
    printf("%d\n",result);
    return 0;
}