boj) 1021 회전하는 큐 (C++)

1. 문제 링크

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

1021번: 회전하는 큐

2. 문제 개요

 큐가 원형 큐의 형태를 띠고 있을 때, 주어진 순서대로 원소를 뽑아내는데 최소한의 연산수를 구하는 문제

 

3. 문제 힌트

 다음 상태는 신경쓰지말고 주어진 상태에서 최대한 적은 연산으로, 즉, 왼쪽으로 돌릴지 오른쪽으로 돌릴지 판단하기.

 

4. 문제 풀기

큐를 Deque로 선언한다.

그리고 1~N까지 삽입한뒤 뽑아내고자 하는 순서에 맞게 Find함수를 사용하여 Queue의 몇 번째에 위치하는지 구한다.

 

              iter

Deque : O O O O O O O O O O

이처럼 2번째에 위치한다면,

왼쪽으로 연산을 진행했을경우 1번 -> iter - deque.begin()으로 구할 수 있고

오른쪽으로 연산을 진행했을경우 N - 왼쪽 연산 수로 구할 수 있다.(size함수로 구할 수 있음)

위에서 구한 두 값을 사용해서 어느쪽이 더 적은 연산으로 진행할 수 있는지 판단하고

그에 맞춰 큐를 변화시켜주면 된다. 

 

5. 코드

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

int main()
{
	deque<int> ret;
	int sol = 0;
	int order[50];

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < m; ++i)
		cin >> order[i];

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

	for (int i = 0; i < m; ++i)
	{
		deque<int>::iterator iter;
		
		iter = find(ret.begin(), ret.end(), order[i]);
		
		int left = 0, right = 0;
		int len = ret.size();

		left = iter - ret.begin();	//except me
		right = len - left;	//include me

		if (left < right)
		{
			for (int j = 0; j < left; ++j)
			{
				int temp = ret.front();
				ret.pop_front();
				ret.push_back(temp);
				sol++;
			}
			ret.pop_front();
		}
		else
		{
			for (int j = 0; j < right;++j)
			{
				int temp = ret.back();
				ret.pop_back();
				ret.push_front(temp);
				sol++;
			}
			ret.pop_front();
		}
	}
	cout << sol;

	return 0;
}     

 

지적, 댓글 언제나 환영입니다~