백준 1021: 회전하는 큐

문제 요약

양방향 순환 큐에서 주어진 조건에 따라 몇 개의 원소를 순차적으로 뽑아 내고자 할 때, 최소의 연산 횟수를 출력하는 문제

큐에서 사용할 연산은 다음과 같다.

• 첫 번째 원소를 뽑아낸다.
• 큐를 왼쪽으로 한 칸 이동시킨다.
• 큐를 오른쪽으로 한 칸 이동시킨다.

문제 분류

• 자료 구조
• 덱

문제 풀이

시간도 널널하고 해서 그냥 while문으로 왼쪽으로 돌렸을 때와 오른쪽으로 돌렸을대의 횟수를 전부 구한뒤, 적은 값을 더하는 방식으로 했다.

자료구조는 list를 사용하여 구현하였다. 다른 자료 구조로도 좋지만, 맨 끝과 맨 앞의 삽입 삭제라면 배열보다는 리스트가 나을 거라 생각했다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <list>

using namespace std;

int main()
{
	int n, m, cnt = 0, lcnt, rcnt, input;
	int ary[51];
	list<int> dq, cp;

	cin >> n >> m;
	for (int i = 0; i < m; i++)
		scanf("%d", &ary[i]);

	for (int i = 0; i < n; i++)
		dq.push_back(i + 1);

	for (int i = 0; i < m; i++) {
		lcnt = 0;
		rcnt = 0;
		cp = dq;
		while (cp.front() != ary[i]) {
			input = cp.front();
			cp.pop_front();
			cp.push_back(input);
			lcnt++;
		}
		cp = dq;
		while (cp.front() != ary[i]) {
			input = cp.back();
			cp.pop_back();
			cp.push_front(input);
			rcnt++;
		}
		dq = cp;
		dq.pop_front();
		cnt += min(lcnt, rcnt);
	}
	cout << cnt;

	return 0;
}