[백준] 1021번 회전하는 큐 (C++, DEQUE)

 

왼쪽으로 빼는게 더 적은지 오른쪽으로 빼는게 더 빠른지 본 뒤 해당 위치로 이동시켜준다 (덱 사용)

뒤로 빼는 경우 맨 뒤 위치에서 앞으로 이동시켜주는 것까지 포함이라 (앞에서만 빼므로) +1 해준다.

 

#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <deque>
using namespace std;

int n;

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n,m,x;
	deque<int> dq;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		dq.push_back(i+1);
	}
	int sum = 0;
	for (int i = 0; i < m; i++) {
		cin >> x;//위치

		int left = 0,right=0;
		for (int j = 0; j < dq.size(); j++) {
			if (x == dq[j]) {
				break;
			}
			left++;
		}
		for (int j = dq.size()-1; j >=0; j--) {
			if (x == dq[j]) {
				break;
			}
			right++;
		}
		right += 1;
	
		if (left<=right) {
			sum += left;

			while (left--) {
				dq.push_back(dq.front());
				dq.pop_front();
			}
			dq.pop_front();
			
		}
		else {
			sum +=right;
	
			while (right--) {
				dq.push_front(dq.back());
				dq.pop_back();
			}
			dq.pop_front();
		}
	}

	cout << sum << "\n";

	return 0;
}