[BOJ 백준] 1021번 회전하는 큐 / C++

문제

---

문제를 보시려면 링크를 클릭해주세요.

풀이

---

STL deque를 사용하여 풀었습니다.

1. 뽑으려는 수의 위치가 왼쪽, 오른쪽 중 어느 방향과 더 가까운지를 판별합니다.
2. 왼쪽, 오른쪽 중 이동 횟수가 적은 방향으로 push, pop을 실행합니다.
3. left ＞ right 조건의 경우는 push, pop 횟수보다 이동횟수가 +1이므로 cnt++ 를 한 번 더 해줍니다.
4. 총 이동 횟수의 합을 출력합니다.

소스 코드

---

#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char**argv) {

	ios::sync_with_stdio(0);
	cin.tie(0);
		
	deque<int> DQ;
	int N, M;
	int left, right;
	int cnt = 0;
	
	cin >> N >> M;
	
	for(int i=1; i<=N; i++){
		DQ.push_back(i);
	}
	

	while(M--){
		int num;
		cin >> num;
		
		for(int i=0; i<DQ.size(); i++){
			
			if(DQ[i] == num){
				left = i;
				right = DQ.size()-i;
				break;
				
			}
		}
		
		if(left<=right){
			while(1){
				if(DQ.front()==num)
					break;

				DQ.push_back(DQ.front());
				DQ.pop_front();
				cnt++;
				
			}
			DQ.pop_front();
		}
		
		else{
			cnt++;
			while(1){
				if(DQ.back()==num)
					break;
	
				DQ.push_front(DQ.back());
				DQ.pop_back();
				cnt++;
				
			}
			DQ.pop_back();
		}

	}
	
	cout << cnt;
	
	return 0;
}