회전하는 큐 (feat. 백준, 1021번)

회전하는 큐
https://www.acmicpc.net/problem/1021

1021번: 회전하는 큐

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, M, total = 0;
	deque<int> ans;
	cin >> N >> M;
	for (register int n = 1; n <= N; ++n)
		ans.push_back(n);
	for (register int m = 0, v, pos1, pos2; m < M; ++m) {
		cin >> v;
		pos1 = distance(ans.begin(), find(ans.begin(), ans.end(), v));
		pos2 = ans.size() - pos1;
		total += min(pos1, pos2);
		if (pos1 <= pos2) {
			while (pos1--)
				ans.push_back(ans.front()), ans.pop_front();
			ans.pop_front();
		}
		else {
			while (pos2--)
				ans.push_front(ans.back()), ans.pop_back();
			ans.pop_front();
		}
	}
	cout << total;
	return 0;
}
// *&)*@*

1. 문제로 주어진 뽑아야할 번호에 대해서 앞에서 빼는 경우, 뒤에서 빼는 경우의 최소 횟수를 카운팅하는 문제입니다.
2. 문제의 3가지 연산중 첫번째는 '항상 pop_front한다' 라는 것입니다.