백준[1021] 회전하는 큐

문제 설명

문제 링크

http://icpc.me/1021

1021번: 회전하는 큐

풀이

덱을 이용하여 풀 수 있다.

덱에서 뽑을 수의 위치를 찾아서 그 위치가 덱의 중간지점보다 오른쪽에 있다면 3번을 덱의 첫 번째에 원하는 수가 위치할 때까지 반복하고, 중간지점보다 왼쪽에 있다면 2번을 첫 번째에 원하는 수가 위치할 때까지 반복한다.

코드

#include <cstdio>
#include <deque>
#include <algorithm>

using namespace std;

int main() {
    deque<int> dq;
    int n, m; scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        dq.push_back(i);
    }
    int ans = 0;
    while (m--) {
        int k; scanf("%d", &k);
        for (int i = 0; i < dq.size(); i++) {
            if (dq[i] == k) {
                if (i > dq.size() / 2) {
                    while (dq.front() != k) {
                        dq.push_front(dq.back());
                        dq.pop_back();
                        ans++;
                    }
                    dq.pop_front();
                } else {
                    while (dq.front() != k) {
                        dq.push_back(dq.front());
                        dq.pop_front();
                        ans++;
                    }
                    dq.pop_front();
                }
                break;
            }
        }
    }
    printf("%d", ans);
}