[백준/BOJ] 백준 1021번 : 회전하는 큐

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

1021번: 회전하는 큐

deque를 사용하여, 첫 번째 원소 뽑아내기, 뽑아 내려는 수가 앞에 가까이 있을 때는 왼쪽으로 한칸 이동시키기 또는 뽑아 내려는 수가 뒤에 가까이 있을 때 오른쪽으로 한칸 이동시키기를 이용해 문제를 해결했다.

 

코드

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

int n, m;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	deque<int> dq;
	vector<int> pick;
	int input;
	int temp;
	int cnt = 0;

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		dq.push_back(i);

	for (int i = 0; i < m; i++)
	{
		cin >> input;
		pick.push_back(input);
	}

	for (int i = 0; i < pick.size(); i++)
	{
		int front_check = 0;
		int back_check = dq.size() - 1;

		while (1)
		{
			//첫번째 원소 뽑아내기
			if (dq[0] == pick[i])
			{
				dq.pop_front();
				break;
			}

			//뽑아 내려는 수가 앞에 가까이 있을때
			//왼쪽으로 한칸 이동 시키기
			if (dq[front_check] == pick[i])
			{
				temp = dq.front();
				dq.pop_front();
				dq.push_back(temp);
				cnt++; //2번연산 횟수 추가

				front_check = 0;
				back_check = dq.size() - 1;
			}

			//뽑아 내려는 수가 뒤에 가까이 있을때
			//오른쪽으로 한칸 이동 시키기
			else if (dq[back_check] == pick[i])
			{
				temp = dq.back();
				dq.pop_back();
				dq.push_front(temp);
				cnt++; //3번연산 횟수 추가

				front_check = 0;
				back_check = dq.size() - 1;
			}

			else
			{
				front_check++;
				back_check--;
			}
		}
	}

	cout << cnt;

	return 0;
}