[백준 알고리즘/C++/큐, 덱] 1021 회전하는 큐

 

 

큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐의 크기 N, 뽑아내려고 하는 수의 개수 M

뽑아내려고 하는 수의 위치가 순서대로 주어졌을 때 2번, 3번 연산의 최솟값을 출력하는 문제

 

 

덱을 이용하면 쉽다! 양방향으로 뺐다 넣었다..

최솟값을 출력하라고 했으니 뽑아내려고 하는 수의 위치가 덱의 앞쪽이면 front의 원소를 뒤로 보내는게 빠르고,

뽑아내려고 하는 수의 위치가 덱의 뒤쪽이라면 반대로 back의 원소를 앞으로 보내는게 빠르다

덱의 front가 뽑아내려고 하는 수와 일치할 때 까지 결과값에 1씩 더해주면 된다

 

코드를 보면 쉬움

 

 

#include <iostream>
#include <deque>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n, m, val, res = 0;
    deque<int> dq;
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        dq.push_back(i);
    }
 
    int idx;
    while (m--) {
        cin >> val;
 
        //위치찾기
        for (int i = 0; i < n; i++) {
            if (dq[i] == val) {
                idx = i;
                break;
            }
        }
        
        //idx(위치)가 앞쪽에 있을 때
        if (idx <= dq.size() / 2) {
            while (dq.front() != val) {
                dq.push_back(dq.front());
                dq.pop_front();
                res++;
            }
        }
        //idx(위치)가 뒤쪽에 있을 때
        else {
            while (dq.front() != val) {
                dq.push_front(dq.back());
                dq.pop_back();
                res++;
            }
        }
 
        dq.pop_front();
    }
 
    cout << res;
}