[알고리즘] 회전하는 큐

구현 방식

• 목표 원소의 위치를 찾아서, 그 위치가 dq 의 앞에 위치하는지 뒤에 위치하는지 확인

int main(void)
{
	int N, M;
	cin >> N >> M;
	deque<int> dq = deque<int>(N, -1);
	for (int i = 0; i < M; i++)
	{
		int idx;
		cin >> idx;
		dq[idx - 1] = i;
	}
	solution(M, dq);
}


void solution(int M, deque<int>& dq)
{
	int dest = 0;
	int result = 0;
	while (dest < M && !dq.empty())
	{
		int curr = dq.front();
		if (curr == dest)
		{
			dq.pop_front();
			dest++;
		}
		else
		{
			int destIdx = 0;
			for (int i = 0; i < dq.size(); i++) { if (dq[i] == dest) destIdx = i; }
			if (destIdx > dq.size() / 2)
			{
				while (dest != dq.front())
				{
					dq.push_front(dq.back());
					dq.pop_back();
					result++;

				}
			}
			else
			{
				while (dest != dq.front())
				{

					dq.push_back(dq.front());
					dq.pop_front();
					result++;
				}

			}
			dq.pop_front();
			dest++;
		}
	}
	cout << result;
}