[백준]회전하는 큐

유의할점

풀이

덱을 이용하면 reverse하지 않아도 원소를 빼낼수있다.

원소를 빼는 과정은 2번을 사용하거나 3번을 사용해야한다. 둘이 섞어서 사용하는 경우는 무조건 최적이 아니다.

코드

C++

#include <iostream>
#include <algorithm>
#include <deque>
#include <queue>

using namespace std;

int second(int n, deque<int> &dq) {
	int res = 0;
	while (dq.front()!=n) {
		res++;
		dq.push_back(dq.front());
		dq.pop_front();
	}
	dq.pop_front();
	return res;
}

int third(int n, deque<int> &dq) {
	int res = 0;
	while (dq.front()!=n) {
		res++;
		dq.push_front(dq.back());
		dq.pop_back();
	}
	dq.pop_front();
	return res;
}

int main() {
	queue<int> q;
	deque<int> dq;
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		dq.push_back(i);
	}
	int M;
	cin >> M;
	for (int i = 0; i < M; i++) {
		int _;
		cin >> _;
		q.push(_);
	}
	int res = 0;
	while (!q.empty()) {
		deque<int> sq = dq;
		deque<int> tq = dq;
		int i = second(q.front(), sq);
		int j = third(q.front(), tq);
		if (i > j) {
			dq = tq;
			res += j;
		}
		else {
			dq = sq;
			res += i;
		}
		q.pop();
	}
	cout << res;
}