1021번

1021번 - 회전하는 큐

처음에 문제를 잘못읽었다. 문제에서 주어진 순서대로 출력하는게 아닌, 세개를 출력하는 방법의 최솟값인 줄 알았다.

그래서 문제를 풀었더니 너무나 어려웠다.. 근데 문제를 다시 읽어보니 순서대로 출력하는 문제였다.

그래서 deque 를 써서 문제를 쉽게 풀 수 있었다.

목표로 하는 번호가 앞에서 가까운지, 뒤에서 가까운지를 파악한 후에

앞에서 가까우면 front 에서 pop 해서 back에서 push 를 해주면 되고, 뒤에서 가까우면 back 에서 pop 해서 front 에 push를 하면 된다.

(해당하는 번호가 deque 의 0번 인덱스에 올 때까지)

그러면서 이러한 과정이 몇번 일어나는지 숫자를 세주면 된다.

##문제를 제대로 읽는 습관을 갖자

<정답 코드>

#include<iostream>
#include<queue>
#include<deque>
using namespace std;
 
int main()
{
    int n, m;
    cin >> n >> m;
    deque<int> dq(n);
    queue<int> out;
    for (int i = 0; i < n; i++)
    {
        dq[i] = i + 1;
    }
    
    for (int i = 0; i < m; i++)
    {
        int tmp;
        cin >> tmp;
        out.push(tmp);
    }
 
    int ans = 0;
 
    while (m!=0)
    {
        int need = out.front();
 
        int pos;
 
        for (int i = 0; i < dq.size(); i++)
        {
            if (dq[i] == need)
            {
                pos = i;
            }
        }
 
        if (pos == 0)
        {
            m--;
            dq.pop_front();
            out.pop();
            continue;
        }
 
        int front_distnace = pos;
        int back_distance = dq.size() - pos;
 
        if (front_distnace <= back_distance)
        {
            ans += front_distnace;
 
            while (front_distnace--)
            {
                int front = dq.front();
                dq.push_back(front);
                dq.pop_front();
            }
        }
        else
        {
            ans += back_distance;
 
            while (back_distance--)
            {
                int back = dq.back();
                dq.push_front(back);
                dq.pop_back();
            }
        }
    }
 
    cout << ans << "\n";
    return 0;
}