[알고리즘/문제풀이/BOJ 1021번] 회전하는 큐

회전하는 큐는 데크를 사용하여 푸는 문제입니다. front에서만 pop이 될 수 있으므로 뽑아낼 원소의 위치와 front사이의  가능한 두 개의 거리를 비교하여 거리가 작은 쪽으로 로테이션합니다. 뽑아낼 원소를 모두 뽑아내기 위해 로테이션하는 총 횟수를 계산하여 출력함으로써 문제를 해결할 수 있습니다.

작성한 코드는 다음과 같습니다.

---

#include<stdio.h>
#define size 100

int N, M;
int extracted[100];
int index_extracted;
int total_op;

int deque[size];

int front = 0, back = 1;
int temp_front, temp_back;

void rotate_clock() {
	deque[back]=deque[(front+1+size)%size];
	back = (back+1) % size;
	front = (front + 1) % size;
	return;
}

void rotate_counterclock() {
	deque[front] = deque[(back - 1 + size) % size];
	back = (back - 1+size) % size;
	front = (front -1+size) % size;
	return;
}

void pop_front() {
	front = (front + 1) % size;
	return;
}

int main(void) {
	scanf("%d %d", &N, &M);

	for (int i = 0; i < M; i++) {
		scanf_s("%d", &extracted[i]);
	}

	for (int i = 1; i <= N; i++) {
		deque[i] = i;
	}
	back = N + 1;

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < (back-front+size-1)%size; j++) {
			if (deque[(front+1+j)%size] == extracted[i]) {
				index_extracted = (front+1+j)%size;
				break;
			}
		}
		temp_front = front;
		temp_back = back;
		if (((index_extracted - temp_front - 1+size)%size) > (temp_back - index_extracted+size)%size) {
			for (int j = 0; j < ((temp_back - index_extracted + size)%size); j++) {
				rotate_counterclock();
				total_op++;
			}
			pop_front();
		}
		else {
			for (int j = 0; j < ((index_extracted - temp_front - 1 + size) % size); j++) {
				rotate_clock();
				total_op++;
			}
			pop_front();
		}
	}

	printf("%d\n", total_op);
}

문제의 지문은 다음 링크에서 확인할 수 있습니다.

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