1021) 회전하는 큐 c++

문제 ) www.acmicpc.net/problem/1021

1021번: 회전하는 큐

 

풀이 ) 

맨 처음 큐의 크기 N을 입력받으면 1~N 까지의 수를 가진 큐를 갖게 되고, M 번 뽑는다.

지민이가 뽑는 카드를 target 이라는 변수로 입력을 받고,

target 이 맨앞에 있다면 바로 pop_front 를해서 없앴고,

맨 앞에 있지 않다면 왼쪽으로 회전할지, 오른쪽으로 회전할지 정해야한다.

회전을 정하는 방법은 덱을 처음부터 돌면서 target 이 현재 덱에서 몇 번 째에 있는지 idx 를 이용해서 셌다.

큐의 전체 크기를 2로 나누고 +1 을 해서 그 값과 idx 값을 비교해서

(dq.size()/2) +1 의 값이 idx 보다 크다면 왼쪽으로 한 칸씩 이동하고
반대의 경우라면 오른쪽으로 한 칸씩 이동하도록 했다.  

 

코드 )

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

int N, M, cnt, target, tmp;
string cmd;
deque<int> dq;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	for(int i=1; i<=N; i++) dq.push_back(i);

	while(M--) {
		cin >> target;

		if(target == dq.front())
			dq.pop_front();
		else {
			int idx = 0;
			for( int e: dq){
				if( e == target){
					idx++;
					break;
				}
				idx++;
			}

			if(idx > (dq.size()/2)+1) {
				while(dq.front() != target) {
					tmp = dq.back();
					dq.push_front(tmp);
					dq.pop_back();
					cnt++;
				}
			}

			else{
				while(dq.front() != target) {
					tmp = dq.front();
					dq.push_back(tmp);
					dq.pop_front();
					cnt++;
				}
			}
			dq.pop_front();
		}
	}

	cout << cnt << "\n";
}