백준 알고리즘 1021번: 회전하는 큐 [C++]

문제 출처: https://www.acmicpc.net/problem/1021

1021번: 회전하는 큐

1. 코드

#include <iostream>
#include <deque>

using namespace std;

int main()
{
	int n, m, sum = 0;
	int *arr;

	cin >> n >> m;
	arr = new int[m];
	deque <int> d;
	for (int i = 0; i < n; i++)			//1부터 n까지 입력
		d.push_back(i + 1);

	for (int i = 0; i < m; i++)			//찾고자하는 수 입력
		cin >> arr[i];
	
	for (int i = 0; i < m; i++)
	{
		int cnt1 = 0, cnt2 = 0;
		deque <int> d1(d);
		deque <int> d2(d);

		while (d1.front() != arr[i])	//오른쪽 방향으로 진행
		{
			d1.push_back(d1.front());
			d1.pop_front();
			cnt1++;
		}

		while (d2.back() != arr[i])		//왼쪽 방향으로 진행
		{
			d2.push_front(d2.back());
			d2.pop_back();
			cnt2++;
		}

		if (cnt1 > cnt2)		//왼쪽 방향으로 가는 것이 빠른 경우
		{
			sum += cnt2 + 1;
			d2.pop_back();
			d = d2;
		}
		else					//오른쪽 방향으로 가는 것이 빠른 경우
		{
			sum += cnt1;
			d1.pop_front();
			d = d1;
		}
	}
	cout << sum;
	delete[]arr;
}

(실행)

2. 풀이

먼저 덱에 1부터 n까지의 수를 넣고, 찾고자하는 m개의 수를 배열에 저장한 뒤 왼쪽으로 가는 경우와 오른쪽으로 가는 경우의 횟수 중 가장 작은 것을 택한 뒤 반복하면 된다.

int n, m, sum = 0;
int *arr;

cin >> n >> m;
arr = new int[m];
deque <int> d;
for (int i = 0; i < n; i++)			//1부터 n까지 입력
	d.push_back(i + 1);

for (int i = 0; i < m; i++)			//찾고자하는 수 입력
	cin >> arr[i];
	

n과 m의 수를 입력 후 1부터 n까지의 수를 덱에 저장하고, 찾고자하는 m개의 수를 입력한다.

for (int i = 0; i < m; i++)
{
	int cnt1 = 0, cnt2 = 0;
	deque <int> d1(d);
	deque <int> d2(d);

	while (d1.front() != arr[i])	//오른쪽 방향으로 진행
	{
		d1.push_back(d1.front());
		d1.pop_front();
		cnt1++;
	}

0부터 m까지 반복하는데 d1과 d2에 d를 복사하고 d1의 제일 앞의 수가 찾고자 하는 수와 같지 않다면 같아질 때까지 d1의 제일 앞의 수를 제일 뒤로 옮기는데 그 횟수를 측정한다.

while (d2.back() != arr[i])		//왼쪽 방향으로 진행
{
	d2.push_front(d2.back());
	d2.pop_back();
	cnt2++;
}

그 후 d2는 제일 뒤에 있는 값이 찾고자하는 수가 아니라면 같아질 때까지 제일 뒤에 있는 수를 제일 앞으로 옮기며 그 횟수를 측정한다.

if (cnt1 > cnt2)		//왼쪽 방향으로 가는 것이 빠른 경우
{
	sum += cnt2 + 1;
	d2.pop_back();
	d = d2;
}
else					//오른쪽 방향으로 가는 것이 빠른 경우
{
	sum += cnt1;
	d1.pop_front();
	d = d1;
}

그리고 측정한 횟수 중 가장 회수를 저장하고 덱을 pop해준다. 그 다음에 해당 덱을 복사한다. 왼쪽방향으로 진행하는 경우 +1을 더한 값을 저장하냐면 시작점이 제일 뒷쪽이 아닌 제일 앞쪽에서 진행하기 때문이다.

3. 느낀점

생각보다 어려웠지만 막상 해결하고나니 그렇게 어려운 느낌이 없는 문제였다. 개인적으로 회전하는 큐보다는 회전하는 덱이 아닌가 싶다.