[알고리즘/C++] 백준 1021. 회전하는 큐

- 그림으로 그려보니 풀이가 확실히 보였던 문제.

- 예제 입력 2를 푼다고 해보자. 원형으로 배치한 순열이 입력 n=10이기 때문에 1~10으로 입력된 숫자이고, m은 길이 3의 숫자를 찾을 것이고, 두번째 줄의 2,9,5를 순서대로 찾을 예정이라고 한다.

- 원형 순열을 원형 다이얼을 돌려가면서 찾는다고 하면 꽤 괜찮은 풀이법이 나온다고 본다. 이 다이얼을 시계/반시계 중 어느쪽으로 돌려야 빠르게 찾을 수 있는가를 생각해보자. 결국 한쪽으로 돌릴 때랑 반대쪽으로 돌릴 때 중 짧은 길이를 더해가며 계산하면 간단히 풀리는 문제이다.

- 바킹독 님의 알고리즘 https://blog.encrypted.gg/935?category=773649 강의를 참조하며 풀었기 때문에 deque 자료구조로 문제를 해결했다.

#include <iostream>
#include <deque>
using namespace std;

int main() {
	// your code goes here
	deque<int> a, b;
	int n, m;
	cin >> n >> m;
	for(int i = 0 ; i < n ; i++){
		a.push_back(i+1);
	}
	for(int i = 0 ; i < m ; i++){
		int k;
		cin >> k;
		b.push_back(k);
	}
	
	int cnt = 0;
	int front=0, back=0;
	while(!b.empty()){
		if(a.front() == b.front()){
			back = a.size() - front;
			cnt += front > back ? back : front;
			a.pop_front();
			b.pop_front();
			front=back=0;
		}
		else{
			a.push_back(a.front());
			a.pop_front();
			front++;
		}
	}
	
	cout << cnt;
	return 0;
}