회전하는 큐

코드

#include<iostream>
#include<deque>
using namespace std;

int main(void) {
	cin.tie(NULL);  ios::sync_with_stdio(false);
	deque<int> dq;
	int N, M;
	int tmp;
	int result=0;
	
	cin >> N >> M;
	int *input = new int[M]; // 2 9 5
	int *index = new int[M]; // 1 8 4 (index에 따라 계속 변함)
	for (int i = 0; i < M; i++) {
		cin >> input[i];
		index[i] = input[i] - 1;
	}
	

	for (int i = 0; i < N; i++) {
		dq.push_back(i+1);
	}
	

	for (int i = 0; i < M; i++) {
		if (input[i] == dq.front()) {
			dq.pop_front();
		}
		else if (dq.size() / 2 >= index[i]) {
			while (input[i] != dq.front()) {
				result++;
				tmp = dq.front();
				dq.pop_front();
				dq.push_back(tmp);
				for (int j = i; j < M; j++) {
					if (--index[j] < 0) { index[j] += dq.size(); }
				}
			}dq.pop_front();
		}
		else if (dq.size() / 2 < index[i]) {
			while (input[i] != dq.front()) {
				result++;
				tmp = dq.back();
				dq.pop_back();
				dq.push_front(tmp);
				for (int j = i; j < M; j++) {
					if (++index[j] >= dq.size()) { index[j] -= dq.size(); }
				}
			}dq.pop_front();
		}
		
		for (int j = i; j < M; j++) {
			if (--index[j] < 0) { index[j] += dq.size(); }
		}
	}
	cout << result;

	return 0;
}

참고

+> https://blockdmask.tistory.com/73
+> https://numerok.tistory.com/137