1021번: 회전하는 큐 (백준 온라인 저지, C++)

문제 풀이

 

빼고자 하는 숫자의 위치를 파악한 후, 2번 연산과 3번 연산 중 더 적게 수행할 수 있는 연산을 수행하여, 1번 연산을 시행하면 문제를 쉽게 풀 수 있습니다.

 

 

코드

 

#include <iostream>
#include <deque>
 
using namespace std;
 
int n, m, cnt;
deque <int> dq;
 
void _op2() {
 
    int a = dq.front();
    
    dq.pop_front();
    dq.push_back(a);
    cnt++;
 
    return;
}
 
void _op3() {
 
    int a = dq.back();
 
    dq.pop_back();
    dq.push_front(a);
    cnt++;
 
    return;
}
 
int main() {
 
    cnt = 0;
    cin >> n >> m;
 
    for(int i = 1; i <= n; i++) {
        dq.push_back(i);
    }
 
    while (m--) {
        
        int t = 0;
        int now; cin >> now;
 
        for (int i = 0; i < dq.size(); i++) {
            if (dq[i] == now) {
                t = i;
                break;
            }
        }
 
        if (t < dq.size() - t) {
            for (int i = 0; i < t; i++) {
                _op2();
            }
        }
        else {
            for (int i = 0; i < dq.size() - t; i++) {
                _op3();
            }
        }
        dq.pop_front();
    }
    cout << cnt << '\n';
 
    return 0;
}

 

 

제출 결과

 

 

 

문제 출처

 

https://www.acmicpc.net/problem/1021

1021번: 회전하는 큐