[백준] 1021번 회전하는 큐

문제: 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강 - 덱

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

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

백준 1021번 회전하는 큐: C언어 풀이 :: 수서곤충의 세계

백준 1021번 회전하는 큐: C언어 풀이