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

풀이과정

양방향 순환 큐의 원소의 개수와 뽑을 원소의 개수 int N, M 그리고 뽑을 원소의 위치 deque<int> req를 입력 받는다. 1부터 N까지를 담고 있는 deque<int> arr도 정의해준다.

int N, M;
deque<int> arr, req;

cin >> N >> M;
req = deque<int>(M);
FOR(i, M)
	cin >> req[i];

arr = deque<int>(N);
FOR(i, N)
	arr[i] = i + 1;

2와 3의 연산 횟수를 나타내는 int step을 정의하고 작업을 시작한다.

1. 지금 뽑을 원소의 위치를 담을 int target_pos를 정의하고, 그 위치를 저장한다.

2. 그 위치가 arr.size() / 2 보다 작다면 2의 연산을 하는 것이 유리하다.

2-1. arr.front()가 지금 뽑을 원소일 때까지 front를 back으로 옮긴다. 이 때, 매번 step에 1씩 더한다.

2-2. 반복이 끝나면 arr.front()가 지금 뽑을 원소가 되는 것은 자명하다. arr.front()와 req.front()를 모두 pop해준다.

3. 그 위치가 arr.size() / 2 보다 크다면 3의 연산을 하는 것이 유리하다.

3-1. arr.front()가 지금 뽑을 원소 일 때까지 back을 front로 옮긴다. 이 때, 매번 step에 1씩 더한다.

3-3. 반복이 끝나면 arr.front()가 지금 뽑을 원소가 되는 것은 자명하다. arr.front()와 req.front()를 모두 pop 해준다.

int step = 0;
while (req.size()) {
	int target_pos = 0;
	while (arr[target_pos] != req.front()) target_pos++;
	if (target_pos < (arr.size() / 2)) {
		while (arr.front() != req.front()) {
			arr.push_back(arr.front());
			arr.pop_front();
			++step;
		}
		arr.pop_front();
		req.pop_front();
	}
	else {
		while (arr.front() != req.front()) {
			arr.push_front(arr.back());
			arr.pop_back();
			++step;
		}
		arr.pop_front();
		req.pop_back();
	}
}

그리고 결과를 출력해주면 끝.

cout << step << EL;

예제 테스트

두 번째 예제에서 오류가 발생한다. 3-1. 부분에서 req.pop_back() 이게 문제다. req.pop_front()로 수정한 후 이상없다.

네 번째 예제에서 답이 다르다. 정답: 14, 오답: 16.

2. 부분에서 <를 <=로 고쳤다. 왜냐하면 앞에서 뒤로 보내는 것보다 뒤에서 앞으로 가져올 때 원하는 원소를 발견하기 위해 더 많은 연산이 필요하기 때문이다.

이를 고친 이후 예제는 정답과 같아졌다.

결과 코드

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N, M;
	deque<int> arr, req;

	cin >> N >> M;
	req = deque<int>(M);
	FOR(i, M)
		cin >> req[i];

	arr = deque<int>(N);
	FOR(i, N)
		arr[i] = i + 1;

	int step = 0;
	while (req.size()) {
		int target_pos = 0;
		while (arr[target_pos] != req.front()) ++target_pos;

		if (target_pos <= (arr.size() / 2)) {
			while (arr.front() != req.front()) {
				arr.push_back(arr.front());
				arr.pop_front();
				++step;
			}
			arr.pop_front();
			req.pop_front();
		}
		else {
			while (arr.front() != req.front()) {
				arr.push_front(arr.back());
				arr.pop_back();
				++step;
			}
			arr.pop_front();
			req.pop_front();
		}
	}

	cout << step << EL;

	return 0;
}

제출 결과