[BOJ] 1021번 : 회전하는 큐

1. problem :

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std; 

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

	int ans = 0;
	int N, M;
	cin >> N >> M; 
	deque<int> D; 
	for (int i = 1; i <= N; i++) {
		D.push_back(i);
	}
	while (M--) {
		int count2 = 0, count3 = 0;
		int x; 
		cin >> x; 
		deque<int> dq2(D); 
		deque<int> dq3(D);
		while (true) {
			if (dq2.front() != x) {
				count2++;
				dq2.push_back(dq2.front());
				dq2.pop_front();
			}
			else {
				dq2.pop_front();
				break;
			}
		}
		while (true) {
			if (dq3.back() != x) {
				count3++;
				dq3.push_front(dq3.back());
				dq3.pop_back();
			}
			else {
				count3++;
				dq3.pop_back();
				break;
			}
		}
		if (count2 >= count3) {
			ans += count3;
			D = dq3;
		}
		else {
			ans += count2;
			D = dq2;
		}
	}
	cout << ans << '\n';
	return 0;
}

 

3. solution 2 :

#include <bits/stdc++.h>
using namespace std; 

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

	int ans = 0;
	int N, M;
	cin >> N >> M; 
	deque<int> D; 
	for (int i = 1; i <= N; i++) {
		D.push_back(i);
	}
	while (M--) {
		int x;
		cin >> x;
		int idx = find(D.begin(), D.end(), x) - D.begin();
		while (D.front() != x) {
			if (idx < (int)D.size() - idx) {
				D.push_back(D.front()); 
				D.pop_front();

			}
			else {
				D.push_front(D.back());
				D.pop_back();
			}
			ans++;
		}
		D.pop_front();
	}
	cout << ans << '\n';
	return 0;
	
}

<source code 출처: https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x07/solutions/1021.cpp >