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

문제

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

문제 설명

 

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

풀이

이 문제는 1 ~ n까지 저장되어있는 Deque에 1, 2, 3번 연산을 이용하여 두 번째 줄에 입력된 숫자를 순서대로 pop하는 문제이다.

 

이때, 2, 3번 연산의 최솟값을 출력하면 된다.

 

왼쪽으로 이동할 때, 오른쪽으로 이동할 때의 연산 값을 구한 뒤, 두 연산중, 최솟값인 방향으로 Deque를 이동시키는 방법으로 풀이했다. 

#include <bits/stdc++.h>

using namespace std;

void MoveCollection(deque<int> &q, int dir)
{
	if(dir > 0)
	{
		q.push_front(q.back());
		q.pop_back();
	}
	else
	{
		q.push_back(q.front());
		q.pop_front();
	}
}

int GetMove(deque<int> q, int target ,int dir )
{
	int count = 0;
	while(q.front() != target)
	{
		MoveCollection(q, dir);
		count += dir;
	}
	return count;
}

void MoveDeque(deque<int> &q, int value)
{
	int move = abs(value);
	int dir = value > 0 ? 1 : -1;
	
	for(int i = 0; i < move; i++)
	{
		MoveCollection(q, dir);
	}

	q.pop_front();
}

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

	deque<int> q;
	int n, m;

	cin >> n >> m;

	for(int i = 1; i <= n; i++)
	{
		q.push_back(i);
	}

	int count = 0;
	for(int i = 0; i < m; i++)
	{
		int input;
		cin >> input;

		int left = GetMove(q, input, -1); 
		int right = GetMove(q, input, 1); 
		int value = abs(left) < right ? left : right;
		
		count += abs(value);

		MoveDeque(q, value);
	}

	cout << count;
	return 0;
}