[BOJ] 회전하는 큐(1021)

[백준(BOJ)] 회전하는 큐(1021) C++

문제 : BOJ_1021번 회전하는 큐

문제 설명

Deque

1 ~ N까지의 수가 양방향 순환 큐에 나열되어 있는 상태에서 M 개의 원소를 뽑아야 합니다.
이때 나열되어 있는 방식이 순환 큐이기 때문에 첫 번째 위치의 원소만 뽑아낼 수 있고, 첫 번째 위치가 아니라면 순환으로 왼쪽 혹은 오른쪽으로 회전하며 원소를 첫 번째 위치로 이동시켜 뽑아야 합니다.
이때 왼쪽 오른쪽으로 회전하는 횟수의 최소를 구해야 합니다.


Solution

N이 50보다 작기 때문에 무슨 방법을 쓰든 구현만 해낸다면 정답 처리가 될 것입니다.
저는 deque을 사용했는데, 이유는 다음과 같습니다.

  • 첫 번째 원소를 삽입, 삭제할 수 있다.
  • 마지막 원소를 삽입, 삭제할 수도 있다.
  • 인덱스를 순회하면서 해당 인덱스 안에 어떤 수가 들어있는지 확인할 수 있다. 왼쪽이나 오른쪽으로 순회하기 전, 인덱스를 순회하여 해당하는 수가 몇 번째 인덱스에 있는지 확인하고, 그 인덱스와 deque.size()를 비교하며 왼쪽으로 옮길지, 오른쪽으로 옮길지 정하면서 진행하면 해결할 수 있습니다.

Description

  • 실제로 예제를 만들어 놓고, 예제에서 deque의 전체 사이즈와 인덱스를 비교해보고 식을 짜면 편합니다.

#include <iostream>
#include <deque>
#include <vector>
using namespace std;
int main(void) {
	int N, M;
	cin >> N >> M;
	deque<int> d;
	for (int i = 1; i <= N; i++) d.push_back(i);
	int result = 0;
	for (int i = 0; i < M; i++) {
		int now;
		cin >> now;
		int idx = 0;
		for (int i = 0; i < d.size(); i++) {
			if (now == d[i]) {
				idx = i + 1;
				break;
			}
		}
		if (idx-1 < d.size() - idx+1) {
			result += idx - 1;
			for (int i = 1; i < idx; i++) {
				int val = d.front();
				d.push_back(val);
				d.pop_front();
			}
			d.pop_front();
		}
		else {
			result += d.size() - idx+1;
			for (int i = 1; i <= d.size() - idx; i++) {
				int val = d.back();
				d.push_front(val);
				d.pop_back();
			}
			d.pop_back();
		}
	}
	cout << result << '\n';
	return 0;
}