1021번 회전하는 큐

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

1021번: 회전하는 큐

---

---

<알고리즘>

 1) queue/deque에 1~N까지의 숫자를 차례대로 입력

 2) 찾고자 하는 수 역시 차례대로 vector에 입력

 3) 찾고자 하는 숫자가 0이 될때까지 아래 반복

    3-1) queue의 첫번째 값이 vector에 첫번째 값과 같으면 둘다 pop

    3-2) queue의 첫번째 값이 vector에 첫번째 값과 다르면 찾고자 하는 값이 queue의 어디에 있는지 index 파악

    3-3) index와 queue의 사이즈 비교를 통해 해당 값의 오른쪽에 값이 많으면 2번연산

    3-4)  index와 queue의 사이즈 비교를 통해 해당 값의 왼쪽에 값이 많으면 3번연산

 4) vector의 size가 0이 되면 종료 & 2,3번 연산 실행 횟수 count 출력

 

 

 

STL <deque> 이용 ( 메모리 : 2016KB   시간 : 0ms)

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

int main() {
	int N = 0;
	int M = 0;
	cin >> N >> M;
	
	vector<int>number(M);
	int a = 0;
	for (int i = 0; i < M; i++) {
		cin >> a;
		number[i] = a;
	}

	deque<int>dq;
	for (int i = 1; i <= N; i++) {
		dq.push_back(i);
	}

	int count = 0;
	while (number.size() != 0) {
		//1번 연산
		if (number.front() == dq.front()) {
			number.erase(number.begin());
			dq.pop_front();
		}
		else {
			int index = 0;
			for (int k = 0; k < dq.size(); k++) {
				if (dq[k] == number.front()) {
					index = k;
				}
			}
			//2번연산
			if ((dq.size()-index)>(dq.size()/2)) {
				++count;
				dq.push_back(dq.front());
				dq.pop_front();
			}
			//3번 연산
			else {
				++count;
				dq.push_front(dq.back());
				dq.pop_back();
			}
		}
	}
	cout << count << "\n";
	return 0;
}