[백준/C,C++] 1021번: 회전하는 큐

www.acmicpc.net/problem/1021

1021번: 회전하는 큐

C++에서 제공되는 deque container를 사용하여 쉽게 해결할 수 있습니다.

deque<int> dq;
int res;

void moveLeft(int cnt)
{
    for (int i = 0; i < cnt; i++) {
        dq.push_back(dq.front());
        dq.pop_front();
        res++;
    }
}

void moveRight(int cnt)
{
    for (int i = 0; i < cnt; i++) {
        dq.push_front(dq.back());
        dq.pop_back();
        res++;
    }
}

왼쪽으로 이동하는 함수와 오른쪽으로 이동하는 함수입니다. 왼쪽으로 이동할 땐 제일 앞의 원소를 뒤에 삽입한 후 제일 앞의 원소를 뺍니다. 오른쪽으로 이동할 땐 그 반대입니다. 한 번 연산될 때마다 res(연산 횟수)를 증가시킵니다.

int main(void)
{
    int n, m; cin >> n >> m;
    int front = 0;
    int rear = n - 1;

    for (int i = 1; i <= n; i++) {
        dq.push_back(i);
    }
    for (int i = 0; i < m; i++) {
        int tmp; cin >> tmp;
        for (deque<int>::iterator iter = dq.begin(); iter < dq.end(); iter++) {
            if (tmp == *iter) {
                int f_dis = abs(iter - dq.begin());
                int r_dis = abs(iter - dq.end());
                f_dis <= r_dis ? moveLeft(f_dis) : moveRight(r_dis);
                dq.pop_front();
                break;
            }
        }
    }
    cout << res;

    return 0;
}

찾으려는 원소를 입력받고 덱에서 해당 원소가 위치한 iterator를 찾아 거리를 계산합니다. 좀 더 가까운 쪽으로 해당 거리만큼 이동한 후 원소를 제거합니다. 그러고 나서 총 2, 3번의 연산 횟수(res)를 출력해주면 됩니다.

#include<iostream>
#include<deque>
#include<vector>

using namespace std;

deque<int> dq;
int res;

void moveLeft(int cnt)
{
    for (int i = 0; i < cnt; i++) {
        dq.push_back(dq.front());
        dq.pop_front();
        res++;
    }
}

void moveRight(int cnt)
{
    for (int i = 0; i < cnt; i++) {
        dq.push_front(dq.back());
        dq.pop_back();
        res++;
    }
}

int main(void)
{
    int n, m; cin >> n >> m;
    int front = 0;
    int rear = n - 1;

    for (int i = 1; i <= n; i++) {
        dq.push_back(i);
    }
    for (int i = 0; i < m; i++) {
        int tmp; cin >> tmp;
        for (deque<int>::iterator iter = dq.begin(); iter < dq.end(); iter++) {
            if (tmp == *iter) {
                int f_dis = abs(iter - dq.begin());
                int r_dis = abs(iter - dq.end());
                f_dis <= r_dis ? moveLeft(f_dis) : moveRight(r_dis);
                dq.pop_front();
                break;
            }
        }
    }
    cout << res;

    return 0;
}