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

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

1021번: 회전하는 큐

---

 문제 풀이 

문제에서 3가지 연산이 주어진다.

1번 연산은 첫 번째 원소를 뽑는 연산, 2번 연산은 왼쪽으로 회전, 3번 연산은 오른쪽으로 회전이다.

문제의 포인트는 어느 방향으로 회전할지 정하는 것이다.

타깃이 되는 값의 인덱스를 저장해 begin으로부터의 거리(left)와 end로부터의 거리(right)를 비교한다.

타깃 값을 저장하는 큐가 빌 때까지 연산을 반복한다!

left > right라면 3번 연산을 실행한다. 이때 반복 횟수는 1회 더 많으므로 연산 횟수를 조심한다.

반대로, left < right라면 2번 연산을 실행한다.

 느낀 점

그렇게 어렵지 않은 문제이다. 문제를 해결하고 다른 분들의 코드를 살펴봤는데 더 어렵게 짜신 분도 있었고 더 쉽게 짜신 분도 있었다. 쉽게 짜신 분은 나처럼 따로 타깃 값을 저장하지 않고 바로바로 연산을 실행하셨는데 나보다 코드가 더 짧고 깔끔했다.

 코드

#include <iostream>
#include <deque>
#include <queue>

using namespace std;

int n, m, input, idx;
int cnt = 0;
deque<int> dq;
queue<int> q;

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

	cin >> n >> m;

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

	for (int i = 0; i < m;i++) {
		cin >> input;
		q.push(input);
	}

	while (!q.empty()) {
		if (dq.front() == q.front()) {
			dq.pop_front();
			q.pop();
		}
		else {
			for (int i = 0; i < dq.size();i++) {
				if (q.front() == dq[i]) {
					idx = i;
					break;
				}
			}
			int to_end = dq.size() - idx - 1;
			if (idx > to_end) { 
				for (int i = 0; i <= to_end;i++) {
					dq.push_front(dq.back());
					dq.pop_back();
					cnt++;
				}
			}
			else {
				for (int i = 0; i < idx;i++) {
					dq.push_back(dq.front());
					dq.pop_front();
					cnt++;
				}
			}
		}
	}

	cout << cnt;
}