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

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

 

 

문제

큐의 크기 N(1<=N<=50)과 뽑아내려고 하는 수의 개수 M(1<=M<=N)이 주어진다.뽑아내려고 하는 수의 위치가 순서대로 주어진다. 큐의 첫 번째 원소를 뽑아내거나, 큐를 왼쪽으로 회전시키거나, 오른쪽으로 회전시키는 행동을 할 수 있을 때 모든 수를 뽑아내기 위해 최소 몇 번의 회전이 필요한지 출력한다.

 

풀이

리스트로 iter값 이동시키며, 직접 수를 뽑아낸다. 이때 인덱스 처리 순서와 반환 값에 주의한다.

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

int n, m, x, cnt = 0;
list<int>l;
list<int>::iterator iter;


int main() {

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		l.push_back(i);
	}

	iter = l.begin();
	for (int i = 0; i < m; i++) {
		cin >> x;
		if (l.size() == 1) break;
		list<int>::iterator iterL = iter;
		int cntL = 0;
		while (*iterL != x) {
			if (iterL == l.begin()) iterL = l.end();
			iterL--;
			cntL++;
		}

		list<int>::iterator iterR = iter;
		int cntR = 0;
		while (*iterR != x) {
			iterR++;
			cntR++;
			if (iterR == l.end()) iterR = l.begin();
		}
		cnt += min(cntR, cntL);
		iter = l.erase(iterR);
		if (iter == l.end()) iter = l.begin();
	}

	cout << cnt;
}