[코딩테스트] [BOJ1021] 회전하는 큐

문제

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

---

풀이

1. 양방향 순환 큐기 때문에 deque로 구현해준다.

2. 입력받은 큐의 크기만큼 deque에 원소를 삽입한다.

3. m번만큼 반복하며 현재 뽑아낼 수를 입력받는다.
   3-1. std::find로 deque를 순회하며 현재 뽑아낼 수의 인덱스를 찾는다.
   3-2. 왼쪽으로 회전하게 되면 인덱스 만큼 회전하게 되고, 오른쪽으로 회전하게 되면 덱의 크기 - 인덱스 만큼 회전하게 된다.
   3-3. 왼쪽/오른쪽 회전 수를 비교해 deque에서 pop/push 반복해준다.

4. pop/push 반복할 때마다 증가시킨 totalCount 출력한다.

---

코드

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

int main()
{
	int n = 0, m = 0;
	cin >> n >> m;

	deque<int> field;
	for (int i = 0; i < n; i++)
	{
		field.push_back(i);
	}

	int totalCount = 0;
	for (int i = 0; i < m; i++)
	{
		int current = 0;
		cin >> current;
		--current;

		int currentIndex = find(field.begin(), field.end(), current) - field.begin();
		int leftCount = currentIndex;
		int rightCount = field.size() - currentIndex;

		// 왼쪽으로 회전
		if (leftCount <= rightCount)
		{
			while (field.front() != current)
			{
				field.push_back(field.front());
				field.pop_front();
				totalCount++;
			}
		}
		else
		{
			while (field.front() != current)
			{
				field.push_front(field.back());
				field.pop_back();
				totalCount++;
			}
		}
		
		field.pop_front();
	}

	cout << totalCount;

	return 0;
}