백준 1021 - 회전하는 큐

www.acmicpc.net/problem/1021

 

덱에 들어있는 원소의 정확한 내용물은 정해지지 않았으므로 원소의 순서로 붙여진 숫자를 원소라 봐도 무방하다.

 

N과 M이 크지 않으므로 각 원소를 제거하기 위해 왼쪽으로 회전하는 경우, 오른쪽으로 회전하는 경우를 나눠 둘 중 연산 횟수가 적은 쪽을 택하면 된다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int n, m;
deque<int> dq;
int cnt;
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        dq.push_back(i + 1);
 
    while (m--)
    {
        int num;
        cin >> num;
        int l = 0, r = 0;
 
        deque<int> b = dq, f = dq;
        int x;
 
        while (f.front() != num)
        {
            x = f.front();
            f.pop_front();
            f.push_back(x);
            ++l;
        }
 
        while (b.front() != num)
        {
            x = b.back();
            b.pop_back();
            b.push_front(x);
            ++r;
        }
 
        if (l > r)
            cnt += r, dq = b;
        else
            cnt += l, dq = f;
 
        dq.pop_front();
    }
 
    cout << cnt;
}