백준 1021번 회전하는 큐

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

 

아이디어:

1. 덱에 1~n까지 push_back

2. 덱에서 tmp의 위치를 찾는게 중요

int idx = find(DQ.begin(), DQ.end(), tmp) - DQ.begin()으로 위치를 찾는다.

tmp를 가리키는 반복자에서 시작을 가리키는 반복자인 DQ.begin()을 빼서 구한다.

3. idx가 DQ의 가운데(DQ.size() / 2)보다 작거나 같다면 앞쪽에 위치하니까 front()를 뒤로 보내준다.

4. 아니라면 뒤쪽에 위치하니까 back()을 앞으로 보내준다.

5. 이동 할 때마다 ans++ 해서 마지막에 출력

 

주의사항:

이 문제에는 해당하지 않지만

1. tmp가 DQ에 없으면 find()는 DQ.end()를 가리키므로 idx가 DQ.size()를 초과할 수 있다.

2. DQ.size()는 unsigned int 또는 unsigned long long 형이므로 idx가 DQ.size()보다 크다면 오버플로우가 발생할 수 있으므로 (int) DQ.size()라고 형변환을 해주는 것이 좋다.

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M, tmp, ans = 0;
	deque<int> DQ;
	cin >> N >> M;
	
	for (int i = 1; i <= N; i++)
		DQ.push_back(i);

	while (M--) {
		cin >> tmp;
		int idx = find(DQ.begin(), DQ.end(), tmp) - DQ.begin();
		if (idx <= DQ.size() / 2) {
			while (DQ.front() != tmp) {
				DQ.push_back(DQ.front());
				DQ.pop_front();
				ans++;
			}
		}
		else {
			while (DQ.front() != tmp) {
				DQ.push_front(DQ.back());
				DQ.pop_back();
				ans++;
			}
		}
		DQ.pop_front();
	}

	cout << ans;

	return 0;
	
}