[백준] 1021번 회전하는 큐 C++

semi·2022년 8월 17일
0

coding test

목록 보기
33/57

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

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

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	deque<int> dq;
	queue<int> v;
	int N, M, tmp, answer = 0;
	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> tmp;
		v.push(tmp);
	}
	for (int i = 1; i <= N; i++)
	{
		dq.push_back(i);
	}
	while (!v.empty())
	{
		int target = v.front();
		int front_cnt = 0;
		int back_cnt = 0;
		int min_cnt = 0;
		deque<int> dq_cp1 = dq, dq_cp2 = dq;
		tmp = dq_cp1.front();
		while (1)
		{
			if (dq_cp1.front() == target)
				break;
			front_cnt++;
			dq_cp1.pop_front();
			dq_cp1.push_back(tmp);
			tmp = dq_cp1.front();
		}
		tmp = dq_cp2.front();
		while (1)
		{
			if (dq_cp2.back() == target)
				break;
			back_cnt++;
			tmp = dq_cp2.back();
			dq_cp2.pop_back();
			dq_cp2.push_front(tmp);
			tmp = dq_cp2.back();
		}

		answer += min(front_cnt, back_cnt + 1);
		if (front_cnt <= back_cnt)
		{
			for (int i = 0; i < front_cnt; i++)
			{
				tmp = dq.front();
				dq.pop_front();
				dq.push_back(tmp);
			}
			dq.pop_front();
		}
		else
		{
			for (int i = 0; i < back_cnt; i++)
			{
				tmp = dq.back();
				dq.pop_back();
				dq.push_front(tmp);
			}
			dq.pop_back();
		}
		
		v.pop();
	}
	cout << answer;
	return 0;
}

0개의 댓글