[1021] 회전하는 큐

---

https://www.acmicpc.net/problem/1021

1021번: 회전하는 큐

덱 문제이다.

 

덱(deque)은 양방향에서 push, pop이 가능한 큐이다.

 

궁금한 원소가 주어졌을 때 해당 원소가 빠져나가는데 필요한 2번 연산과 3번 연산의 횟수를 구하는 문제이다. 

** 1번 연산은 횟수에 포함되지 않음! **

연산 횟수의 최솟값은 어떤 기준으로 구분하는게 좋은지 고민하면 된다.

 

 

N=10, M=3, 순서대로 2, 9, 5의 연산 횟수 최솟값이 궁금할 때의 예시이다.

난 해당하는 원소가 어디있는지 인덱스를 찾아서,

해당 원소가 인덱스 절반보다 뒤에 있다면 3번 연산을, 아니라면 2번 연산을 진행하였다.

 

첫번째 상황에서 2는 인덱스 절반을 기준으로 왼쪽에 있으므로 2번 연산을 1번 진행하였다.

두번째 상황에서 9는 인덱스 절반을 기준으로 오른쪽에 있으므로 3번 연산을 3번 진행하였다.

세번째 상황에서 5는 인덱스 절반을 기준으로 왼쪽에 있으므로(가운데에 있어도 왼쪽에 있다고 간주) 2번 연산을 4번 진행하였다.

 

그래서 총 연산 횟수가 8번이 나왔다.

 

아래는 전체 코드이다.

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

int N, M; int cnt;
deque<int> mydeq;
deque<int> order;

void calc_left() {
	// 2번 연산
	int tmp = mydeq.front();
	mydeq.pop_front();
	mydeq.push_back(tmp);
	cnt++;
}

void calc_right() {
	// 3번 연산
	int tmp = mydeq.back();
	mydeq.pop_back();
	mydeq.push_front(tmp);
	cnt++;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		mydeq.push_back(i);
	}

	for (int i = 0; i < M; i++)
	{
		// 궁금한 순서 입력 받기
		int tmp; cin >> tmp;
		order.push_back(tmp);
	}

	while (1) {
		// order가 비어있으면 끝
		if (order.empty()) break;
		int mid = mydeq.size() / 2; // 중간 인덱스 찾기
		int idx;
		// 원하는 원소의 위치 찾기
		for (int i = 0; i < mydeq.size(); i++)
		{
			if (mydeq[i] == order.front()) {
				// 원하는 원소라면
				idx = i;
				break;
			}
		}
		if (idx <= mid) {
			// 2번 연산 수행
			while (1) {
				if (mydeq.front() == order.front()) {
					mydeq.pop_front();
					order.pop_front();
					break;
				}
				calc_left();
			}
		}
		else {
			// 3번 연산 수행
			while (1) {
				if (mydeq.front() == order.front()) {
					mydeq.pop_front();
					order.pop_front();
					break;
				}
				calc_right();
			}
		}

	}

	cout << cnt;
}