[백준 1021]회전하는 큐

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

1021번: 회전하는 큐

요구사항

1. 최소 연산으로 주어진 숫자를 꺼내기

 

풀이

1. 현재 뽑고자 하는 수가 어디에 있는지 찾기

2. 최소가 될 수 있도록 뽑는다

 - size/2보다 클 경우 뒤에서 앞으로 이동 시켜주고, 아닐 경우 앞에서 뒤로 이동시킨다.

3. 정답 출력

 

 

#include <iostream>

using namespace std;

int q[10000];

struct queue {
	int head = 5000;
	int tail = 5000;
	int size = 0;
	int pop_front()
	{
		size--;
		return q[head++];
	}
	int pop_back()
	{
		size--;
		return q[--tail];
	}
	void push_back(int data)
	{
		q[tail++] = data;
		size++;
	}
	void push_front(int data)
	{
		q[--head] = data;
		size++;
	}
	int front()
	{
		return q[head];
	}

	int back() {
		return q[tail];
	}
};

int cnt = 0;
queue Myq;
void solve(int f)
{
	int num = 0;
	//cout << "solove" << endl;
//	cout << endl;
	for (int i = Myq.head; i < Myq.tail; i++)
	{
		num++;
		if (q[i] == f)
		{
			break;
		}
	}
	double size = Myq.tail- Myq.head;
//	cout << "num " << num <<" "<< size<< endl;

	if (num < size/2+1)
	{
	//	cout << "low" << endl;
		for (int i = 1; i < num; i++)
		{
			cnt++;
			int now= Myq.pop_front();
			Myq.push_back(now);
	//		cout << "now" << now << endl;
		}
		Myq.pop_front();
		
	}
	else {
	//	cout << "high" << endl;
		for (int i = 0; i <= size-num; i++)
		{
			cnt++;
			int now = Myq.pop_back();
			Myq.push_front(now);
	//		cout << "now" << now << endl;
		}
		Myq.pop_front();
	}

	
}
int main()
{
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		Myq.push_back(i);
	}
	for (int i = 0; i < m; i++)
	{
		int x;
		cin >> x;
		solve(x);

	}
	cout << cnt << endl;
}