[백준 C++] 1021. 회전하는 큐

문제 링크

---

1021번: 회전하는 큐

접근 방법

---

1. 양방향으로 삽입해야 하므로 deque를 사용합니다.
2. 어느 방향으로 이동시켜야 최솟값이 나오는지 생각합니다.

소스 코드

---

#include <iostream>
#include <deque>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	deque<int> sequence; // 1 ~ n 으로 초기화 시킬 덱입니다.
	int size, t, num, idx, cnt = 0; 

	cin >> size >> t;
	for (int i = 1; i <= size; ++i) // 1부터 n으로 덱 초기화
		sequence.emplace_back(i);

	while (t--)
	{
		cin >> num;

		idx = 0;
		while (sequence[idx] != num) // 덱에서 num의 인덱스를 찾습니다.
			++idx;
		
		if (idx << 1 <= size) // 왼쪽으로 옮기는 연산이 최소일 때
		{
			cnt += idx;
			while (idx)
			{
				sequence.emplace_back(sequence.front());
				sequence.pop_front();
				--idx;
			}
			sequence.pop_front();
		}

		else // 오른쪽으로 옮기는 연산이 최소일 때
		{
			cnt += (idx = size - idx);
			while (idx)
			{
				sequence.emplace_front(sequence.back());
				sequence.pop_back();
				--idx;
			}
			sequence.pop_front();
		}
		--size;
	}

	cout << cnt;
	return 0;
}

코드 설명

---

변수

1부터 size까지의 수로 초기화된 deque를 사용했습니다.

뽑아내려고 하는 수의 개수를 저장하는 변수 t, deque의 크기인 size, 뽑아내려고 하는 수 num, deque에서 num의 인덱스를 나타내는 변수 idx를 사용했습니다.

cnt는 연산횟수들을 저장하는 변수입니다.

 

코드

덱에서 num의 인덱스를 찾습니다.

인덱스의 값이 size의 절반보다 작으면 왼쪽으로 옮기는 연산 횟수가 최솟값이 되고, 그렇지 않으면 오른쪽으로 옮기는 연산 횟수가 최솟값이 됩니다.

if 문에서 쉬프트 연산을 사용한 이유는 * 연산보다 더 빠르기 때문에 사용했습니다.

왼쪽으로 옮기는 연산을 할 경우, idx만큼 왼쪽으로 옮기는 연산을 하기 때문에 cnt에 idx를 더해준 후, deque에서 왼쪽에서 오른쪽으로 옮겨줍니다.

해당 숫자가 deque의 첫 번째로 옮겨지면, pop을 해줍니다.

else 에서는 size - idx가 연산 횟수가 됩니다. 오른쪽으로 옮기는 연산을 한 후, pop을 해줍니다.

pop을 해서 deque의 size가 하나 작아졌으므로 size를 1만큼 감소시킵니다.