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

문제 링크

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

 

문제 정보

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

풀이

 문제를 이해하는 것이 상당히 힘들었다. 양방향 순환 큐라는 것을 통해 덱을 이용해서 풀이할 수 있다는 것을 생각할 수 있다. 예시를 들어서 문제를 이해해보자. 만약 n = 10에서 4를 뽑아야 한다고 생각해보자.

 덱 : 1 2 3 4 5 6 7 8 9 10

 여기에서 4를 뽑을려면 왼쪽으로 이동해서 뽑는 2번 연산이 오른쪽으로 이동하는 3번 연산보다 더 적은 횟수로 4를 추출할 수 있다는 것을 알 수 있다. 이를 통해 덱에 들어있는 원소의 개수(size)의 절반 보다 앞에 있으면 2번 연산이 더 적은 횟수로 추출할 수 있고, 아니라면 3번 연산이 더 적은 횟수로 추출할 수 있다는 것을 알 수 있다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;
	
	deque<int> DQ;
	
	for (int i = 1; i <= n; i++) {
		DQ.push_back(i);
	}
	
	int ans = 0;
	
	while (m--) {
		int num;
		cin >> num;
		
		int idx = 0;
		for (int i = 0; i < DQ.size(); i++) {
			if (DQ[i] == num) {
				idx = i;
				break;
			}
		}
		
		if (idx <= DQ.size() / 2) { // 덱의 절반보다 앞에 있으면 2번 연산이 더 빠름.
			for (int i = 0; i < idx; i++) {
				DQ.push_back(DQ.front());
				DQ.pop_front();
				ans++;
			}
			DQ.pop_front();
		} else { // 덱의 절반보다 뒤에 있으면 3번 연산이 더 빠름.
			for (int i = 0; i < DQ.size() - idx; i++) {
				DQ.push_front(DQ.back());
				DQ.pop_back();
				ans++;
			}
			DQ.pop_front();
		}
	}
	
	cout << ans;
	
	return 0;
}