BOJ)1021 회전하는 큐

문제: icpc.me/1021

주어진 순서대로 첫번째 원소를 뽑아 원하는 수를 뽑아낼 때 쉬프트 연산의 최소 횟수를 출력하는 문제이다.

쉬프트 연산은 앞 뒤에서 pop push가 가능한 deque을 이용하면 쉽게 해결가능하다 

#include <cstdio>
#include <algorithm>
#include <deque>
using namespace std;
deque<int> dq;
int n, m, x, r;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        dq.push_back(i);
    for (int i = 0; i < m; i++) {
        scanf("%d", &x);
        if (dq.front() == x)
            dq.pop_front();
        else {
            int idx = 0;
            for (auto here : dq) {
                if (here == x)
                    break;
                idx++;
            }
            if ((dq.size() / 2) < idx) {
                while (dq.front() != x) {
                    int y = dq.back();
                    dq.pop_back();
                    dq.push_front(y);
                    r++;
                }
                dq.pop_front();
            }
            else {
                while (dq.front() != x) {
                    int y = dq.front();
                    dq.pop_front();
                    dq.push_back(y);
                    r++;
                }
                dq.pop_front();
            }
        }
    }
    printf("%d\n", r);
    return 0;
}