#1021번 회전하는 큐 (C++)

링크 : www.acmicpc.net/problem/1021

1021번: 회전하는 큐

문제 해석은 다음과 같다. 

1. 큐를 뽑을 경우, 맨 앞의 원소가 제거된다. 

2. 큐에서 값을 왼쪽으로 옮길 경우 a1, a2, ... K 의 순서가 a2 ... K, a1으로 변경된다. 

3. 큐에서 값을 오른쪽으로 옮길 경우 a1, a2, ... aN-1, K의 순서가 K, a1, a2 .... aN-1 으로 변경된다

4. 1부터 N까지의 수가 큐에 누적되고, M개 만큼의 숫자가 주어진다. 

5. M개의 숫자들이 '입력된 순차적으로' 큐에서 제거되기 위해, 최소한으로 사용된 2번과 3번 알고리즘의 합을 구하여라.

 

문제를 대충 읽은 탓에 푸는데 시간이 생각보다 소요됐다. 

문제 풀이는 다음과 같다. 

1. 어차피 큐는 FIFO 알고리즘이다. 즉, 먼저 입력된 값이 먼저 출력 된다. 

2. 차례대로 맨 앞의 값을 빼고 누적하기를 반복한다. 

3. 이때 맨 앞의 값이 원하는 값과 일치하기까지 걸린 누적 카운트를 기억한다.

4. 누적 카운트가 큐의 길이 / 2 보다 클경우, 오른쪽으로 옮겨지는 방식을 사용해야한다. 

때문에 큐의 길이 - 누적 카운트를 진행하고 그 값을 더해준다.

5. 반대로 투적 카운트가 큐의 길이 / 2 이하일 경우, 기존의 큐의 법칙인 FIFO대로 옮겨져야 한다. 

때문에 누적 카운트를 그대로 더해준다. 

 

문제의 카테고리가 큐와 관련되어 큐로 풀었으나,

생각해보니 덱으로 푸는편이 더 빨라보였다. 

귀찮으니 다른 덱 관련 문제가 나올때 덱으로 풀어줘야겠다. 

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;


int main() {
	ios::sync_with_stdio(NULL);
	cin.tie(NULL);

	int n = 0, m = 0, cnt = 0, temp = 0, temp2 = 0, ans = 0, arr[50];
	queue<int>q;
	cin >> n >> m;
	for (int i = 0; i < m; i++) cin >> arr[i];
	for (int i = 1; i <= n; i++) q.push(i);
	while (cnt < m) {
		if (q.front() == arr[cnt]) {
			q.pop();
			cnt++;
		}
		else {
			temp = 0;
			while (q.front() != arr[cnt]) {
				temp2 = q.front();
				q.pop();
				q.push(temp2);
				temp++;
			}
			if (temp > q.size() / 2) ans += q.size() - temp;
			else ans += temp;
		}
	}
	cout << ans << "\n";
	return 0;
}