BOJ (C/C++) 1021번: 회전하는 큐

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

1021번: 회전하는 큐

 

---

풀이

이 문제의 큐에서는 pop_front()만 수행 가능함.뽑으려는 원소의 위치를 파악한 후, 해당 원소가 앞부분과 뒷부분 중 어디와 더 가까운 지 확인하여 2 or 3번 연산을 수행함.

---

코드

#include <stdio.h>
#include <deque>
#include <vector>
using namespace std;

vector <int> V;
deque <int> D;

int Get_cnt(int n, int size) {
	int pop, tmp, loc;
	int cnt = 0;

	for (int i = 0; i < size; i++) {
		pop = V[i];

		loc = 0;
		while (D[loc] != pop) loc++; // 뽑으려는 원소의 위치 파악

		// 원소가 뒷부분에 위치 -> 연산3 (오른쪽 이동)
		if (D.size() - loc < loc) {
			for (int j = 0; j < D.size() - loc; j++) {
				tmp = D.back();
				D.pop_back();
				D.push_front(tmp);
				cnt++;
			}
		}

		// 원소가 앞부분에 위치 -> 연산2 (왼쪽 이동)
		else {
			for (int j = 0; j < loc; j++) {
				tmp = D.front();
				D.pop_front();
				D.push_back(tmp);
				cnt++;
			}		
		}
		// 연산 1
		D.pop_front();
	}
	return cnt;
}
int main() {
	int N, M, n;
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) D.push_back(i + 1);
	for (int i = 0; i < M; i++) {
		scanf("%d", &n);
		V.push_back(n);
	}
	printf("%d", Get_cnt(N, M));

	return 0;
}