[C++] 백준 1021 회전하는 큐

https://www.acmicpc.net/problem/1021
제목 : 회전하는 큐
solved.ac 난이도 : Silver III

나의 풀이

1. 큐에서 데이터를 뽑아내는 곳은 맨 앞 한곳 뿐이다.
2. 지민이가 뽑아내려고 하는 위치의 순서를 따로 큐에 빼놓고
   순서대로 연산을 한다.
3. 원하는 순서의 숫자가 맨앞으로 올 때까지의 회전 횟수를
   왼쪽 회전, 오른쪽 회전 둘다 연산 후 둘 중에 적은 횟수를 사용한다.
4. 원하는 숫자들이 다 뽑힐 때까지 반복한다.

정답 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int calcleftdir(deque<int> nums, int n) {
    int count = 0;
    while (nums.front() != n) {
        nums.push_back(nums.front());
        nums.pop_front();
        count++;
    }
    return count;
}

int calcrightdir(deque<int> nums, int n){
    int count = 0;
    while (nums.front() != n) {
        nums.push_front(nums.back());
        nums.pop_back();
        count++;
    }
    return count;
}

void calc(deque<int> &nums, queue<int> &wait, int &count) {
    while (!wait.empty()) {
        int tmp = wait.front();
        wait.pop();
        int lcount = calcleftdir(nums, tmp), rcount = calcrightdir(nums, tmp);
        if (lcount <= rcount) {
            while (nums.front() != tmp) {
                nums.push_back(nums.front());
                nums.pop_front();
            }
            count += lcount;
        }
        else {
            while (nums.front() != tmp) {
                nums.push_front(nums.back());
                nums.pop_back();
            }
            count += rcount;
        }
        nums.pop_front();
    }
}

int main()
{
    int N, M, index, flg = 0, count = 0;
    cin >> N >> M;
    vector<int> indexs;
    queue<int> wait;
    deque<int> nums;
    for (int i = 0; i < M; i++) {
        cin >> index;
        wait.push(index);
        indexs.push_back(index);
    }
    sort(indexs.begin(), indexs.end());
    for (int i = 1; i <= N; i++) {
        if (flg < indexs.size() && i == indexs[flg]) {
            nums.push_back(i);
            flg++;
        }
        else nums.push_back(0);
    }

    calc(nums, wait, count);
    cout << count;
}

설명

자료구조 deque의 구조를 이해하고 있으면 풀 수 있는 문제입니다.
처음에 자료들을 deque에 넣을 때 주어지는 자료의 위치가 정렬이 되어 있지 않습니다. 그래서 저는 자료들을 일단 vector 배열에 넣어서 정렬을 시킨 다음 deque에 순서대로 자료를 넣는데, vector 배열 안에 없는 숫자들의 위치에는 전부 0을 넣었습니다.

그리고 뽑아내려 하는 자료의 위치를 보관하는 큐를 하나 만들고 순서대로 뽑을 수 있게끔 만듭니다.
그리고 그 큐에서 순차적으로 데이터를 뽑으며 모든 숫자가 저장돼있는 deque를 왼쪽과 오른쪽으로 둘다 회전을 시켜본 다음 적은 횟수의 회전을 수행 하며 회전 횟수를 더해가면 됩니다.

질문과 수정할점 그리고 더 좋은 방법이 있으면 공유 부탁드립니다.