[BOJ] 1021 - 회전하는 큐

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

---

[알고리즘풀이]

왼쪽, 오른쪽으로 회전하는 것을 덱을 이용해 양쪽에서 삽입, 삭제를 진행하면 된다.

덱에 1 ~ n 까지 삽입하고, 원하는 값이 몇 번째에 있는지 구한다.

그러면, 현재 front에서 왼쪽 / 오른쪽 중 어디로 순회하는 것이 적게 이동하는지 판단할 수 있고,

이동하며 횟수를 계속 Count 해주면 된다.

#include<iostream>
#include<deque>
#include<algorithm>

using namespace std;

int m_l[50];

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

	deque<int> dq;
	int n, m, answer = 0;

	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		dq.push_back(i);
	for (int i = 0; i < m; i++)
		cin >> m_l[i];

	for (int i = 0; i < m; i++) {
		if (dq.front() == m_l[i]){
			dq.pop_front();
			continue;
		}
		int inx = 0;
		for (int j = 0; j < dq.size(); j++)
			if (dq[j] == m_l[i])
				break;
			else
				inx = j;
		int r = 0, l = 0;
		// 오른쪽으로간다.
		if (inx < (dq.size() / 2)) {
			while (dq.front() != m_l[i]) {
				int temp = dq.front();
				dq.pop_front();
				dq.push_back(temp);
				r++;
			}
			dq.pop_front();
			answer += r;
		}
		// 왼쪽으로간다.
		else {
			while (dq.front() != m_l[i]) {
				int temp = dq.back();
				dq.pop_back();
				dq.push_front(temp);
				l++;
			}
			dq.pop_front();
			answer += l;
		}
	}
	cout << answer;
}

---