회전하는 큐(1021)

들어가는 말

원형 큐에서 원하는 원소들을 최소한의 움직임으로 뽑아내는 문제이다.
deque를 사용했으며, 왼쪽 혹은 오른쪽으로 돌리다가 맨 앞에 원하는 원소가 오면 멈춘 후 count를 출력해준다.

코드 설명

왼쪽으로 옮기는 방식과 오른쪽으로 옮기는 방식 그리고 어떤 기준으로 옮길지를 혼자 구했다. 그러나 인덱스를 어떻게 찾는지는 구하지 못했다. 어떤 방식으로 풀고 또 어떤 요소들을 써야 할 건 알지만 그걸 하나의 코드로 완성하기는 아직 부족한 느낌... 계속 풀다보면 익숙해지려나.
1. 일단 n과 m을 받는다.
2. n만큼 deque에 넣어준다.
3. m만큼 찾고자 하는 인덱스들을 배열에 넣어준다.
4. 총 m만큼 돌리는데, 먼저 deque를 모두 돌리면서 인덱스와 같은 값이 있는지 찾는다. 즉, 우리가 찾고자하는 숫자이다. 만일 같은 값이 있다면 다른 변수에 저장해 준다.
5. 그 숫자가 deque 사이즈 절반보다 작거나 같으면 왼쪽으로 돌려준다. 왼쪽으로 돌려줄 때마다 count를 더해준다. 만일 값을 찾으면 그 값을 pop_fornt해준다.
6. 조건이 아니면 오른쪽으로 돌려준다. 여기서 반복문은 deque.size() - index다. 나는 여기서 실수를 했는데, 사이즈에다가 인덱스를 빼주어야지만 오른쪽으로 돌려주는 게 된다. 그리고 값을 찾으면 pop_front를 해준다.
7. 전체 반복문이 끝나면 count를 출력해준다.

코드

#include<deque>
#include<iostream>
using namespace std;

int main() {
	//기본 정보
	int n, m, x;
	int index = 0;
	int count = 0;
	deque<int> dq;
	int arr[51];

	cin >> n >> m;

	//dq에 값 넣기
	for (int i = 1; i <= n; i++) {
		dq.push_back(i);
	}

	//찾고자하는 데이터 인덱스 받기
	for (int i = 0; i < m; i++) {
		cin >> x;
		arr[i] = x;
	}

	for (int i = 0; i < m; i++) {

		for (int j = 0; j < n; j++) {
			if (dq.at(j) == arr[i]) {
				index = j;
				break;
			}
		}

		if (index <= dq.size() / 2) {
			for (int k = 0; k < index; k++) {
				dq.push_back(dq.front());
				dq.pop_front();
				count++;
			}
			dq.pop_front();
		}
		else {
			for (int k = 0; k < dq.size() - index; k++) {
				dq.push_front(dq.back());
				dq.pop_back();
				count++;
			}
			dq.pop_front();
		}
	}

	cout << count << endl;
}