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

#include <iostream>
#include <deque>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    cin >> n >> m;
    
    deque<int> d;

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

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

        // input값이 현재 어디에 위치해있는지 찾는다
        int target_index = 0;
        for (int k = 0; k < n; k++) {
            if (d[k] == input) {
                target_index = k;
                break;
            }
        }

        int count_left = 0;
        int count_right = 0;

        if (d.front() != input) {
            // 왼쪽으로 계속 이동시키는 경우 계산
            count_left = target_index;

            // 오른쪽으로 계속 이동시키는 경우 계산
            count_right = d.size() - target_index;
        }
        
        if (count_left <= count_right) {
            result += count_left;
            // 덱 왼쪽 회전
            while (d.front() != input) {
                int temp = d.front();
                d.pop_front();
                d.push_back(temp);
            }
        }
        else if (count_left > count_right) {
            result += count_right;
            // 덱 오른쪽 회전
            while (d.front() != input) {
                int temp = d.back();
                d.pop_back();
                d.push_front(temp);
            }
        }

        d.pop_front();
    }

    cout << result;
}

문제에서 양방향 순환 큐를 활용하는 것으로 명시되어 있으므로 덱을 활용해 해결하는 문제이다.

반복적으로 타겟 값의 위치를 찾고 이 위치를 기반으로 왼쪽 회전과 오른쪽 회전의 연산수를 계산한 뒤, 그 중 더 작은 값을 result에 더하고 해당 방향으로 pop과 push를 반복하며 덱을 회전시킨다.

가장 중요한 것은 왼쪽으로 회전하던, 오른쪽으로 회전하던 타겟 값을 찾아서 pop을 한 시점 직후의 덱 배열은 항상 같다는 것이다.