문제: 1021번: 회전하는 큐
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m; // n: 큐의 크기, m: 뽑아내려고 하는 수의 개수
cin >> n >> m;
deque<int> rotateQueue;
for (int i = 1; i <= n; i++)
rotateQueue.push_back(i);
queue<int> order;
for (int i = 0; i < m; i++) {
int tmp;
cin >> tmp;
order.push(tmp);
}
int totalCnt = 0;
// 현재 큐의 상태를 저장해놓을 원형 큐 2개 만들기
deque<int> dupleQueue1;
deque<int> dupleQueue2;
while (!order.empty()) {
if (rotateQueue.front() == order.front()) {
rotateQueue.pop_front();
order.pop();
}
else {
int tmpCnt1 = 0;
int tmpCnt2 = 0;
dupleQueue1 = rotateQueue;
dupleQueue2 = rotateQueue;
// 왼쪽으로 미는 경우, 오른쪽으로 미는 경우 두가지로 구분하고
// 둘 중 더 연산이 적게 드는 애를 고르기!!
// 일단 왼쪽으로 미는 경우
while (dupleQueue1.front() != order.front()) {
dupleQueue1.push_back(dupleQueue1.front());
dupleQueue1.pop_front();
tmpCnt1++;
}
// 오른쪽으로 미는 경우
while (dupleQueue2.front() != order.front()) {
dupleQueue2.push_front(dupleQueue2.back());
dupleQueue2.pop_back();
tmpCnt2++;
}
// 왼쪽으로 미는게 더 많은 연산이 필요하면 오른쪽으로 미는 경우 채택
if (tmpCnt1 > tmpCnt2) {
rotateQueue = dupleQueue2;
totalCnt += tmpCnt2;
}
else {
rotateQueue = dupleQueue1;
totalCnt += tmpCnt1;
}
}
}
cout << totalCnt << "\n";
return 0;
}
그냥 현재 상태를 저장해놓을 원형큐 2개를 따로 만들어놓고, 이를 업데이트 한 후 다시 현재 큐에 반영해주면 쉽게 해결할 수 있는 문제였다. dequeue 의 사용법만 잘 알고있다면 그냥 특징 이용해서 바로 풀 수 있는 문제인 것 같다.
참고자료:
BaaaaaaaarkingDog | [실전 알고리즘] 0x07강 - 덱
[실전 알고리즘] 0x07강 - 덱
안녕하세요, 오늘도 반갑습니다. 스택과 큐에 이어 이번에는 덱을 다루겠습니다. 목차가 0x02만 바뀌고 계속 똑같습니다. 한 번 눈으로 슥 훑고 넘어가겠습니다. 덱은 Restricted Structure의 끝판왕과
blog.encrypted.gg
[C++] 백준 1021: 회전하는 큐
양방향 순환 큐에서 주어진 조건에 따라 몇 개의 원소를 순차적으로 뽑아 내고자 할 때, 최소의 연산 횟수를 출력하는 문제큐에서 사용할 연산은 다음과 같다.첫 번째 원소를 뽑아낸다.큐를 왼
velog.io
백준 1021번 회전하는 큐: C언어 풀이 :: 수서곤충의 세계
백준 1021번 회전하는 큐: C언어 풀이
백준 1021 회전하는 큐 문제의 C언어 해설입니다.큐의 회전을 구현하는 방법과, 문제에서 필요한 배열의 크기를 계산하는 방법을 설명합니다.전략큐의 회전 횟수를 어떻게 구할 수 있을까?처음엔
chinensis.tistory.com