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

문제

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

1021번: 회전하는 큐

---

문제 요약

N개의 원소를 포함하고 있는 양방향 순환 큐가 있을 때, 세 가지 연산을 할 수 있다.

 

1. 첫 번째 원소를 뽑아낸다.

2. 왼쪽으로 한 칸씩 이동시킨다.

3. 오른쪽으로 한 칸씩 이동시킨다.

 

지민이가 뽑아내려고 하는 원소의 위치가 주어졌을 때, 뽑아내는데 드는 2, 3번 연산의 최솟값을 출력한다.

---

코드

#include <iostream>
#include <deque>

using namespace std;

deque<int> dq;

int n, m, cnt;

// num 원소가 dq에 현재 몇번째 위치에 있는지 반환
int searchIndex(int num) {
	for (int i = 0; i < dq.size(); i++) {
		if (dq[i] == num) {
			return i;
		}
	}
	return -1;
}

// 2번 연산 : 왼쪽 이동
void goLeft() {
	int num = dq[0];
	dq.pop_front();
	dq.push_back(num);
}

// 3번 연산 : 오른쪽 이동
void goRight() {
	int num = dq[dq.size() - 1];
	dq.pop_back();
	dq.push_front(num);
}

int main() {

	cin >> n >> m;
	
	// 원소들의 초기 위치를 저장하는 각 원소들을 deque에 저장
	for (int i = 1; i <= n; i++) {
		dq.push_back(i);
	}

	for (int i = 0; i < m; i++) {
		int num;
		cin >> num;

		// 현재 해당 원소의 위치 탐색
		int idx = searchIndex(num);

		if (idx == 0) {
			dq.pop_front();
			continue;
		}
		else if (idx <= dq.size() / 2) {
			while (dq[0] != num) {
				goLeft();
				cnt++;
			}
			dq.pop_front();
		}
		else {
			while (dq[0] != num) {
				goRight();
				cnt++;
			}
			dq.pop_front();
		}
	}

	cout << cnt;
		
	return 0;
}

---

코드 설명

원소를 왼쪽, 오른쪽에서 모두 삽입/삭제가 가능한 Deque라는 자료구조를 이용한다.

 

먼저 Deque에 원소들의 초기 위치 정보를 순서대로 저장한다.

 

왼쪽에서 삭제를 해야할 원소를 입력 받을 때마다, Deque에서 해당 원소의 위치를 찾는다.

 

그 위치가 현재 Deque의 크기의 절반보다 작으면 왼쪽에서, 크면 오른쪽에서 삭제한다.

 

삭제를 위해 반복문을 돌며 원소가 Deque의 왼쪽 끝에 올 때까지 전체 원소를 이동시킨다.

 

마지막으로 전체 원소를 이동시킨 횟수를 출력한다.