[BOJ] 백준 1021 회전하는 큐 c++ (deque)

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

1021번: 회전하는 큐

---

풀이

이 문제는 덱을 사용하는 문제이다.

2번 방법(왼쪽으로), 3번 방법(오른쪽으로) 중 짧은 거리를 구해서 해당 방법대로 push, pop을 반복한다.

이때 주의할 점은, left < right 인 경우 이동횟수가 +1이므로 최종 cnt에 1을 더해주어야 한다.

---

코드

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

using namespace std;

int N, M;
int ans;

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

	cin >> N >> M;

	deque<int> dq;
	int left, right;
	int cnt = 0;

	for(int i = 1; i <= N; i++)
		dq.push_back(i);

	while(M--) {
		int num;
		cin >> num;

		for(int i = 0; i < dq.size(); i++) {
			if(dq[i] == num) {
				left = i;
				right = dq.size() - i;
				break;
			}
		}
		if(left <= right) {
			while(1) {
				if(dq.front() == num)
					break;
				dq.push_back(dq.front());
				dq.pop_front();
				cnt++;
			}
			dq.pop_front();
		}
		else {
			cnt++;
			while(1) {
				if(dq.back() == num)
					break;
				dq.push_front(dq.back());
				dq.pop_back();
				cnt++;
			}
			dq.pop_back();
		}
	}
	cout << cnt << '\n';
	return 0;
}