[Deque] 1021 회전하는 큐

 

문제에 나온 그대로 하면 풀리는 문제이다.

 

M <= N <= 50 이기 때문에,

최대 O(MN) 시간이 걸리므로 매우 넉넉하게 풀 수 있는 편이다.

 

#include <cstdio>
#include <deque>

using namespace std;
deque<int> deq;
int ans;

void move_left(){
    deq.emplace_back(deq.front());
    deq.pop_front();
}

void move_right(){
    deq.emplace_front(deq.back());
    deq.pop_back();
}

void printDeque(){
    // for (int i=0; i<deq.size(); ++i){
    //     printf("%d ", deq[i]);
    // }
    // printf("\n");
    for (auto it = deq.begin(); it != deq.end(); ++it){
        printf("%d ", *it);
    }
    printf("\n");
}

int main() {
    int n, m, k;
    scanf("%d %d", &n, &m);

    for (int i=1; i<=n; ++i){
        deq.emplace_back(i);
    }

    for (int i=0; i<m; ++i){
        scanf("%d", &k);
        // O(N)
        int cnt = 0;
        for (; cnt < n; ++cnt){
            if (deq[cnt] == k) break;
        }

        if (cnt <= n / 2){
            for (int i=0; i<cnt; ++i) move_left();
            ans += cnt;
        }
        else {
            for (int i=0; i<n - cnt; ++i) move_right();
            ans += n - cnt;
        }
        deq.pop_front();
        n--;
    }
    printf("%d\n", ans);
    return 0;
}