C++ 백준 1021 회전하는 큐

백준 1021

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

1021번: 회전하는 큐

풀이 전 나의 생각

양방향 순환 큐와 탐색 조건이 주어질 때

원하는 위치의 원소값을 얻기 위한 최소 계산 횟수를 구해야 한다.

 

조건

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

- N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수

- 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수

 

과정

탐색 조건을 보면 왼쪽으로 한 칸 이동할 때 맨 앞의 원소가 뒤로가고
반대일 경우엔 맨 뒤의 원소가 앞으로간다.

즉, 주어진 자료의 앞과 뒤를 관리할 수 있는 자료구조가 필요하다는 뜻이고
이를 가능하게 해주는 것이 덱 자료구조다.

 

과정은 다음과 같다.

 

1. 덱의 크기만큼 기본 위치 정보를 넣어준다.

 

2. 입력 받은 위치가 덱의 절반 사이즈보다 작다면 왼쪽 방향이

최소 계산이기 때문에 탐색 조건 2번을 실행한다.

 

3. 반대인 경우엔 탐색 조건 3번을 실행한다. 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>
#include <deque>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	deque<int> dq;
	int N, M, left = 0, idx = 0, ans = 0;
	cin >> N >> M;

	for (int i = 1; i <= N; i++)
	{
		//덱의 크기 N만큼 기본 위치 정보를 넣어준다.
		dq.push_back(i);
	}

	for (int i = 0; i < M; i++)
	{
		int loc;
		cin >> loc;

		for (int j = 0; j < N; j++)
		{
			//입력 받은 위치 저장
			if (dq[j] == loc)
			{
				idx = j;
				break;
			}
		}
		
		//입력 받은 위치가 덱 사이즈의 절반 보다 작다면?
		//최소 계산은 왼쪽 방향
		if (idx <= dq.size() / 2)
		{
			while (true)
			{
				if (dq.front() == loc)
				{
					dq.pop_front();
					break;
				}
				++ans;
				dq.push_back(dq.front());
				dq.pop_front();
			}
		}
		// 반대의 경우 오른쪽 방향
		else
		{	
			while (true)
			{
				if (dq.front() == loc)
				{
					dq.pop_front();
					break;
				}
				++ans;
				dq.push_front(dq.back());
				dq.pop_back();
			}
		}
	}

	cout << ans;
}