[Baekjoon] 1021번: 회전하는 큐

 

 

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

1021번: 회전하는 큐

 

---

 

문제 해결 과정

착안

양방향에서 요소를 삽입(enqueue) 및 제거(dequeue) 할 수 있는 큐 자료 구조인 덱(deque) 자료 구조를 활용하는 것을 유도한 문제인 것 같은데, 다음과 같은 원리에 의해 한 방향으로만 요소를 삽입/제거하는 큐(queue) 자료 구조를 이용해도 문제를 해결할 수 있다.

 

덱의 크기를 $N$, 특정 요소를 맨 앞으로 보내기 위한 2번 연산의 실행 횟수를 $k_2$, 3번 연산의 실행 횟수를 $k_3$ 라고 하면,

$$k_2 + k_3 = N$$

가 성립하므로, 정해진 요소를 맨 앞의 위치로 보내기 위한 최소 연산 횟수는

$$\min(k_2,\space k_3) = \min(k_2,\space N - k_2)$$

이다.

 

구현

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <queue>

using namespace std;

queue<int> q;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, M;
	cin >> N >> M;

	for (int i = 1; i <= N; i++)
		q.push(i);

	int Count = 0;
	while (M--)
	{
		int num;
		cin >> num;

		int cnt = 0;
		while (num != q.front())
		{
			int temp = q.front();
			q.pop();
			q.push(temp);
			cnt++;
		}

		if (cnt > q.size() - cnt)
			cnt = q.size() - cnt;

		q.pop();
		Count += cnt;
	}

	cout << Count << "\n";
	return 0;
}

 

실행 결과