백준 1021번: 회전하는 큐

 

 

 

 

 

 

문제의 1,2,3번 조건을 자알 살펴봐야한다.

덱 문제길래 내맘대로 '양쪽에서 다 뽑아낼수 있다'라고 생각하고 뭐가 문젠지 한참을 헤맸던 문제다.

 

1. 첫번째 원소를 뽑아낸다. 

----> 첫번째 자리에 온 것만 뽑아낼수 있다. 마지막 자리에 온 것은 뽑아낼수 없다.

 

 

 

예를들어 ,

 

 

여기서 9를 뽑아 내려면 pop_back을 한번 하면 되는 것이아니라 

 

 

이렇게 맨앞에 오게한 후에 뽑아낼 수 있다.

맨뒤에서도 뽑아낼수 있다고 착각을 하고 풀면

pop_back을 하는 경우(꼬리쪽이 가까운 경우)마다 1이 모자라게 되어 출력값에 차이가 생긴다.

 

 

 

 

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


int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	//cin 실행속도 향상

	int n, m;
	cin >> n >> m;
	deque<int> dq;
	for (int i = 1; i <= n; i++) {
		dq.push_back(i);
	}

	int count = 0;
	for (int i = 0; i < m; i++) {
		int locate;
		cin >> locate;
		int index;
		for (int j = 0; j < dq.size(); j++) {
			if (dq[j] == locate) {
				index = j;
				break;
			}
		}
		if (index < dq.size() - index) {	//left를 pop
			for (int j = 0; j < index; j++) {
				dq.push_back(dq.front());
				dq.pop_front();
				count++;
			}
			dq.pop_front();
		}
		else  {	//right를 pop
			int s = dq.size();
			for (int j = 0; j < s - index - 1; j++) {
				dq.push_front(dq.back());
				dq.pop_back();
				count++;
			}
			dq.pop_back();
			count++;
		}
		
	}

	cout << count << endl;

	return 0;
}