백준 1021회전하는 큐

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 deque 구조를 이용하여 초기에 원소의 위치를 입력받고 그 원소를 맨 앞으로 위치시켜 뽑아 내는데 push를 몇번 해야 하는지 최소 횟수를 구하는 문제입니다. 

 

저는 이 문제를 우선 순서대로 찾아야 하는 위치의 원소의 현재 위치를 찾은뒤 그 위치가 전체 덱의 사이즈의 1/2 보다 크다면 뒤에서 앞으로 보내고 그렇지 않다면 앞에서 뒤로 보내도록 코드를 작성하였습니다. 해당 위치의 원소를 가장 앞으로 보내기 위해서는 앞의 원소들을 뒤로 보내거나 뒤의 원소들을 앞으로 보내야 하는데 이때 최소 횟수가 되기 위해서는 전체 덱의 사이즈 1/2을 기준으로 판별을 하여야 합니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <deque> 

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	deque<int> dq;
	int N,M;
	int arr[50] = {0, };
	cin >> N >> M;
	 
	for(int i = 1; i <= N; i++)
		dq.push_back(i);
	
	for(int i = 0; i < M; i++) {
		cin >> arr[i];
	}
	
	int n = 0;
	int num = 0;
	while(n < M) {
		int index;
		for(int i = 0; i < N; i++) {
			if(dq[i] == arr[n]) {
				index = i;
				break;
			}
		}
		
		while(1) {
			
			if(dq.front() == arr[n]) {
				dq.pop_front();
				n++;
				break;
			}
			
			if(index>dq.size()/2) {
				int x = dq.back();
				dq.pop_back();
				dq.push_front(x);
				num++;
			}
			else {
				int x = dq.front();
				dq.pop_front();
				dq.push_back(x);
				num++;
			}
	
		}
		
	}
	cout << num;
	return 0;
}