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

문제: www.acmicpc.net/problem/1021

1021번: 회전하는 큐

 

 

문제풀이

 

덱을 순차 탐색하여 뽑아야 하는 숫자의 인덱스를 찾은 후 front에서의 거리와 back에서의 거리를 비교하여 더 적은 쪽으로 덱을 회전시킨다.

 

 

코드

#include <iostream>
#include <deque>

using namespace std;

void funcL(deque<int>& d, int num){
    while(d.front() != num){
        d.push_back(d.front());
        d.pop_front();
    }
    d.pop_front();
}

void funcR(deque<int>& d, int num){
    while(d.back() != num){
        d.push_front(d.back());
        d.pop_back();
    }
    d.pop_back();
}

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

    int N, M;
    cin>>N>>M;

    deque<int> d;
    for(int i=1; i<=N; i++){
        d.push_back(i);
    }

        
    int num, cnt = 0;
    while(M--){
        cin>>num;

        int i=0;
        for(; i<d.size(); i++){
            if(d[i] == num)
                break;
        }
        
        if(i > d.size()-i){
            cnt += d.size()-i;
            funcR(d, num);
        }
        else{
            cnt += i;
            funcL(d, num);
        }
    }

    cout<<cnt;

    return 0;
}

 

 

결과