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

 

1) 문제설명

백준 Online Judge 1021번 회전하는 큐

 

2) 아이디어

STL의 덱을 사용하여 문제를 해결하였다.

덱에 1~N까지 숫자를 차례대로 저장하고 내가 찾고자 하는 숫자의 인덱스를 저장하고 그 값이 덱 사이즈의 절반보다 작다면 2번 연산을 실행, 절반보다 크다면 3번 연산을 실행하고 그 횟수를 카운트하여 출력한다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
deque <int> dq;
int n, m;
int k;
int arr[51];
int cnt = 0;

void secal() { // 왼쪽으로 한 칸 이동시키는 함수
	int temp;
	temp = dq.front();
	dq.pop_front();
	dq.push_back(temp);
	cnt++;
}

void thcal() {  // 오른쪽으로 한 칸 이동시키는 함수
	int temp;
	temp = dq.back();
	dq.pop_back();
	dq.push_front(temp);
	cnt ++;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		dq.push_back(i);
	}
	for (int i = 1; i <= m; i++) {
		cin >> arr[i];
	}

	for (int i = 1; i <= m; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i] == dq.at(j)) { // 덱안에서 내가 뽑고자하는 숫자를 찾는다.
				k = j; // 덱안에 내가 찾고자 하는 숫자의 인덱스를 k에 저장한다.
				break;;
			}
		}

		if (k <= dq.size() / 2) { // 내가 찾고자하는 인덱스가 절반보다 앞쪽에 있을경우
			for (int j = 0; j < k; j++) {
				secal(); // 왼쪽으로 이동시킨다.
			}
			dq.pop_front();
		}
		else if ((k > dq.size() / 2)) {// 내가 찾고자하는 인덱스가 절반보다 뒤쪽에 있을경우
			
			for (int j = 0; j < dq.size()-k; j++) {
				thcal();// 오른쪽으로 이동시킨다.
			}
			dq.pop_front();
		}
	}
	cout << cnt;
}
// 1 2 4 8 9