[ C++ ] #1021 회전하는 큐

 

앞뒤로 넣기 간단한 deque를 이용하면 해결할 수 있을 것 같다.

 

1번도 연산자의 일부라고 생각해서 1번을 사용할 수 있으면 1번을 쓰고

1번을 못쓰는경우에만 2번3번을 써야한다고 생각해서 실버4치고 복잡하다고 생각하고있었다..

 

아직 문제를 많이 안풀어봐서 문제해석능력이 부족한것같다.

 

찾을 숫자는 num이라는 배열에 정리하였고 순서판의 숫자들은 deque에 넣어관리하였다.

 

---

분명 간단하다고 생각했는데...

자꾸 실패해서 보니까 왼쪽이동 오른쪽이동의 규칙이 명확하지 않았다. 

 

그래서 찾아야하는 숫자의 인덱스와 덱의 사이즈의 절반을 비교하여

오른쪽으로 이동할지 왼쪽으로 이동할지 결정하였다.

 

그랬더니 바로 원하는 결과가 나왔다!

 

#include <iostream>
#include<deque>

using namespace std;

int num[50];
int N, M, fre, idx = 0;


int main() {


	deque<int> q;
	deque<int>::iterator iter = q.begin();

	cin >> N >> M;
	for (int i = 0; i < M; i++) {  //찾아야하는 수 배열에 넣기
		cin >> num[i];
	}
	for (int i = 0; i < N; i++) {  //순서대로 숫자넣기
		q.push_back(i + 1);
	}

	for (int i = 0; i < M; i++) {//모든수를 찾을때까지 반복
		int f = (q.size() / 2);
		idx = 0;

		for (iter = q.begin(); iter != q.end(); ++iter) {
			if (num[i] == *iter) break;
			idx++;
		}
		if (num[i] == q.front()) {  //맨앞에 원하는게 있다면 넘기기
			q.pop_front();
			continue;
		}
		
		if (idx <= f) {
			while (q.front() != num[i]) { //왼쪽으로이동
				q.push_back(q.front());
				q.pop_front();
				fre++;
			}q.pop_front();
		}
		else {  //3단계수행
			while (q.front() != num[i]) { //오른쪽으로이동
				q.push_front(q.back());
				q.pop_back();
				fre++;
			}q.pop_front();
		}
	}

	cout << fre;
}