[BaekJoon]백준 1021번 회전하는 큐

 

[BaekJoon]백준 1021번 회전하는 큐

 

 

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

 

 

내코드

 

-처음에 자료구조 선택할때 배열(자유로운 원소 삽입/삭제가 힘듬), stack, queue(양방향 삽입/삭제 불가) 등의 이유와 함께 자료구조에서 양방향 이동이 있는 문제라는 것을 알고 deque을 사용

 

-풀이의 기본틀

-> pop해야하는 원소의 위치를 구해서

-> 만약 left쪽으로 이동하는 경우 연산 횟수 & 만약 right쪽으로 이동하는 경우 연산 횟수를 구해서 더 작은 수를 선택한다

-> 만약 left쪽으로 이동하는 경우 front의 원소를 back에 push_back해주면서 pop_front해준다. 즉, 한칸씩 이동해준다.

-> 이동이 완료되면 주어진 수를 pop_front해준다.

 

 

코드블럭

 

//BaekJoon 1021번 회전하는 큐

#include <iostream>
#include <string>
#include <deque>

using namespace std;

deque<int> dq;
deque<int>::iterator iter;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	//get inputs
	int n, m, i; cin >> n >> m;
	int cnt = 0;

	//initialize
	for (i = 1; i <= n; i++) {
		dq.push_back(i);
	}
	
	//pop elements
	for(i = 0 ; i < m ; i++) {
		//get element
		int element; cin >> element;
		int size = dq.size();
		//element position
		int idx = 1;

		//check where element is placed
		for (iter = dq.begin(); iter < dq.end(); iter++) {
			if (*iter == element) break;
			idx++;
		}

		//calculate left or right
		//+1 to right, bcz have to pop_front
		int left = idx - 1;
		int right = size - idx + 1;

		//move left
		if (left < right) {
			//pop front and push it to back
			for (int j = 0; j < left; j++) {
				dq.push_back(dq.at(0));
				dq.pop_front();
				cnt++;
			}
			//pop element
			dq.pop_front();
		}
		//move right
		else {
			//pop back and push it to front
			for (int j = 0; j < right; j++) {
				dq.push_front(dq.at(size - 1));
				dq.pop_back();
				cnt++;
			}
			//pop element
			//bcz of condition, pop_back now allowed
			dq.pop_front();
		}
	}
	cout << cnt << "\n";
	return 0;
}

 

 

참고

 

https://simsimjae.tistory.com/4

https://hyeonstorage.tistory.com/325

https://blog.encrypted.gg/727?category=773649