회전하는 큐 — 덱으로 최소 이동 (BOJ 1021)

아이디어

• 1..n을 덱에 넣고, 매 타겟 tg에 대해 왼쪽/오른쪽 회전 중 더 적은 쪽으로 돌린 뒤 pop_front().
• 인덱스 tgci를 찾아 tgci <= size/2면 왼쪽 회전 tgci번, 아니면 오른쪽 회전 size - tgci번.
• 회전할 때마다 ans++로 누적.

코드에서 right()는 “앞 → 뒤”(실제 왼쪽 회전), left()는 “뒤 → 앞”(실제 오른쪽 회전) 역할입니다.

복잡도

• 각 타겟마다 인덱스 탐색 O(n) + 회전 최대 O(n/2) → 대략 O(n)
• 전체적으로 O(n·m). (문제 제한에서는 충분히 빠름)

코드

#include <bits/stdc++.h>
using namespace std;

deque<int> dq;
int ans;

void left()
{
    dq.push_front(dq.back());
    dq.pop_back();
}

void right()
{
    dq.push_back(dq.front());
    dq.pop_front();
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        dq.push_back(i + 1);
    }

    int m;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        int tg;
        cin >> tg;

        if (dq.front() == tg)
        {
            dq.pop_front();
        }
        else
        {
            int tgci;
            for (int j = 0; j < dq.size(); j++)
            {
                if (tg == dq[j])
                {
                    tgci = j;
                    break;
                }
            }

            if (dq.size() / 2 >= tgci)
            {
                while (tgci--)
                {
                    right();
                    ans++;
                }
            }
            else
            {

                tgci = dq.size() - tgci;
                while (tgci--)
                {
                    left();
                    ans++;
                }
            }
            dq.pop_front();
        }
    }

    cout << ans;

    return 0;
}

메모

• deque는 operator[] 접근 가능해서 인덱스 탐색이 편합니다.
• 회전은 항상 절반 이하로만 수행하니 불필요한 이동이 없습니다.