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

문제설명

---

입출력 예제

---

개념

　1부터 N까지의 수열 중에서 특정 위치의 수를 최소한으로 회전하며 뽑아내는 문제다. 따라서 왼쪽으로 갈지 오른쪽으로 갈지 판단한 후, 값을 뽑아내면 된다. 이때 양방향으로 선입선출하는 구조이므로 dequeue를 사용하면 편하다. 

---

풀이

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

int main()
{
	int N, M, n, cnt = 0;
	cin >> N >> M;

	deque<int> dq;

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

　수열을 초기화할 기준 원소 N, 몇 번 뽑을지 고르는 정수 M, 뽑아내려고 하는 수의 위치 n, 횟수 cnt를 초기화한다. 그리고 deque 자료 구조를 초기화한 후, 값을 삽입한다.

 

	while (M--)
	{
		cin >> n;

		auto it = find(dq.begin(), dq.end(), n);
		int distance = it - dq.begin();
		bool isLeft = distance <= dq.size() / 2 ? true : false;

		if (isLeft)
		{
			for (int i = 0; i < distance; ++i)
			{
				dq.push_back(dq.front());
				dq.pop_front();
				cnt++;
			}
		}

		else
		{
			distance = dq.size() - distance;

			for (int i = 0; i < distance; ++i)
			{
				dq.push_front(dq.back());
				dq.pop_back();
				cnt++;
			}
		}

		dq.pop_front();
	}

	cout << cnt;
}

　n의 위치를 반복자 iteration과 거리 함수 distance를 이용해 추측한 후, 왼쪽과 오른쪽을 판별한다. 그리고 왼쪽의 경우엔 값을 앞으로 보내야 하므로 push_back(dq.front())를 해주고, 오른쪽의 경우엔 값을 뒤로 보내야 하므로 push_back(dq.back())을 이용해 준다.

 

총합본

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

int main()
{
	int N, M, n, cnt = 0;
	cin >> N >> M;

	deque<int> dq;

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

	while (M--)
	{
		cin >> n;

		auto it = find(dq.begin(), dq.end(), n);
		int distance = it - dq.begin();
		bool isLeft = distance <= dq.size() / 2 ? true : false;

		if (isLeft)
		{
			for (int i = 0; i < distance; ++i)
			{
				dq.push_back(dq.front());
				dq.pop_front();
				cnt++;
			}
		}

		else
		{
			distance = dq.size() - distance;

			for (int i = 0; i < distance; ++i)
			{
				dq.push_front(dq.back());
				dq.pop_back();
				cnt++;
			}
		}

		dq.pop_front();
	}

	cout << cnt;
}