[deque, 덱] 백준 1021번 회전하는 큐 c++ 풀이

BOJ 1021번 회전하는 큐 c++ 풀이

• 랭크 : 실버4
• 백준 1021번 회전하는 큐
  
  
  

문제 정리

1. N개의 원소를 포함하고 있는 양방향 순환 큐가 있다.
2. 첫 번째 원소를 뽑아낸다.
3. 왼쪽으로 한 칸 이동. a1..ak -> a2..ak, a1
4. 오른쪽으로 한 칸 이동 a1...ak -> ak, a1...ak-1
5. 뽑아내려고 하는 원소의 위치가 주어질 때, 원소를 주어진 순서대로 뽑아내는데 필요한 4,5번 연산의 최솟값을 구하여라
   
   
   

문제 접근

1. arr의 idx 번째 수를 맨 앞에 나오게 만들어야 합니다. 그래야 pop해서 순서를 만들 수 있습니다.
2. 최소의 연산을 하기 위해서는 왼쪽으로 움직여서 맨 앞으로 가져오느 경우, 오른쪽으로 움직여서 맨 앞으로 가져오는 경우 모두 해보아야 합니다.
3. 그래서 왼쪽으로 움직여서 idx 번째 수를 맨 앞으로 가져오는 경우 몇 번 움직이는지??
4. 오른쪽으로 움직여서 가져오는 경우 몇 번 움직이는지 체크하여 더 작은 경우로 움직여서 pop합니다.
   
   
   

문제 풀이

1. pop 해야 할 순서를 arr 배열에 저장합니다.
2. deque에 1부터 N까지의 수를 넣어놓습니다.
3. 우선 왼쪽으로 이동시켜 봅니다. 맨 앞에 원하는 수가 왔다면 멈추고, 그렇지 않다면 temp deque에 저장하여 shift 시켜봅니다.
4. 그렇게 왼쪽으로 몇 번 이동시켜야 하는지 left 변수에 저장하고 다시 원상복구 시킵니다.
5. 오른쪽도 마찬가지로 진행합니다.
6. 그리고 더 작은 이동 횟수를 가지는 방법으로 이동시키고 해당 숫자를 pop합니다.
7. 이를 모든 수를 정상적으로 출력할때까지 반복합니다.
8. 그리고 누적된 이동 횟수를 출력합니다.
   
   
   

백준 1021 회전하는 큐 c++ 코드

	#include <iostream>
	#include <deque>
	using namespace std;
	int main() {
	// IO 속도 향상
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N, M;
	cin >> N >> M;
	deque<int> dq;
	int arr[50];
	for (int i = 0; i < M; i++) {
	int a;
	cin >> a;
	arr[i] = a;
	}
	for (int i = 1; i <= N; i++) {
	dq.push_back(i);
	}
	int idx = 0;
	int sum = 0;
	while (idx < M) {
	deque<int> temp;
	int left = 0;
	int right = 0;
	// 왼쪽으로 이동
	while (1) {
	if (dq.front() == arr[idx]) break;
	temp.push_back(dq.front());
	dq.pop_front();
	left++;
	}
	// 원복
	while (temp.size() != 0) {
	dq.push_front(temp.back());
	temp.pop_back();
	}
	// 오른쪽
	while (1) {
	if (temp.size() != 0 && temp.front() == arr[idx]) break;
	// 오른쪽으로 이동
	int back = dq.back();
	dq.pop_back();
	right++;
	// 맨 앞으로 온 값이 원하는 수 인지 check
	temp.push_front(back);
	}
	while (temp.size() != 0) {
	dq.push_back(temp.front());
	temp.pop_front();
	}
	if (left < right) {
	sum += left;
	// 왼쪽으로 민다
	while (left--) {
	int temp = dq.front();
	dq.pop_front();
	dq.push_back(temp);
	}
	dq.pop_front();
	}
	else {
	sum += right;
	// 오른쪽으로 민다
	while(right--){
	int temp = dq.back();
	dq.pop_back();
	dq.push_front(temp);
	}
	dq.pop_front();
	}
	idx++;
	}
	cout << sum << endl;
	return 0;
	}

view raw BOJ1021.cpp hosted with ❤ by GitHub

 

풀이 인증