1021 회전하는 큐.

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

[1021번: 회전하는 큐

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가

www.acmicpc.net](https://www.acmicpc.net/problem/1021)

문제의 쟁점은 크게 2가지 이다.

왼쪽으로 돌릴때가 좋은지, 오른쪽으로 돌릴때가 좋은지를 판단하는 판별식,

그리고 이를 통해 회전 경우마다 회수를 카운트해서

최선의 선택해서 더해주면 문제가 해결된다.

#include <iostream>  
#include <deque>  
#include <vector>  

using namespace std;  

void rotate_left(deque<int>& deq)  
{  
    int pop = deq.front();  
    deq.pop_front();  
    deq.push_back(pop);  
}  

void rotate_right(deque<int>& deq)  
{ 
    int pop = deq.back();  
    deq.pop_back();  
    deq.push_front(pop);  
}  

int findInd(deque<int>&dq, int value)  
{  
    int i;  

    for (i = 0;i < dq.size(); ++i) {  
        if (dq[i] == value)  
            return (i);  
    }  
    return (0); 
}  

void solve(deque<int> dq, vector<int> v, int i, int& cnt)  
{  
    int fnd;  
    if (v.size() == i)
        return ;
    if (dq.front() == v[i]) {  
        dq.pop\_front();  
        i++;  
        return solve(dq, v, i, cnt);  
    }
    fnd = findInd(dq, v[i]);  
    if (fnd > dq.size() - fnd) {  
        while (dq.size() - fnd) {  
            rotate_right(dq);  
            cnt++;  
            fnd++;  
        }  
    } else {  
        while (fnd != 0){  
            rotate_left(dq);  
               cnt++;  
            fnd--;  
        }  
    }  
    solve(dq, v, i, cnt);  
}  

int main()  
{  
    int n;  
    int m;  
    int cnt = 0;  
    cin >> n >> m ;  
    deque<int> deq;  
    vector<int> vec;  
    for (int i = 0; i < n; ++i) {  
        deq.push_back(i + 1);  
    }  
    for (int i = 0; i < m; ++i) {  
        int value;  
        cin >> value;  
        vec.push_back(value);  
    }  
    solve(deq, vec, 0, cnt);  
    cout << cnt;  
    return 0;  
}