[백준] 1021번: 회전하는 큐

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

1021번: 회전하는 큐

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

deque<int> dq;
int N, M;
int arr[50];
int cnt = 0;

void moveLeft() {
	int front = dq.front();
	dq.pop_front();
	dq.push_back(front);
}

void moveRight() {
	int back = dq.back();
	dq.pop_back();
	dq.push_front(back);
}

int find(int a) {
	int i;
	for (i = 0; i < dq.size(); i++) {
		if (a == dq[i]) break;
	}
	return i;
}

void move(int a) {
	int left = find(a);
	int right = dq.size() - left - 1;
	if (left <= right) moveLeft();
	else moveRight();
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) cin >> arr[i];
	for (int i = 1; i <= N; i++) dq.push_back(i);

	for (int i = 0; i < M; i++) {
		while (dq.front() != arr[i]) {
			move(arr[i]);
			cnt++;
		}
		dq.pop_front();
	}
	cout << cnt;
}

 

별로 어렵지 않은 문제.

list나 deque를 사용하면 맨앞뒤 원소의 삽입,삭제를 빠르게 할 수 있으므로 그냥 직관적으로 맨 앞 원소를 맨 뒤로 옮겨주고... 하는 식으로 회전하는 큐를 구현하면 된다.

vector를 이용해서 head 포인터를 선언해서 하는 방법도 있겠지만 굳이 head 포인터까지 써가며 복잡하게 구현할 필요 없을듯!

 

그나저나 list와 deque가 기능이 유사해보여서 인터넷에 찾아봤더니, 뜯어보면 완전히 다른 녀석들이었다.

list => linked list로 구현

deque => 청크(일정한 크기의 블록)단위로 메모리를 할당

 

쓰고 보니 list로 구현하는게 더 좋았을 것 같다. input size가 작아서 상관없긴 하지만.

 

vector, deque, list 비교 정리: http://egloos.zum.com/sweeper/v/2817817

vector, deque, list 간단 비교 정리