백준 s4 1021 회전하는 큐 c++

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

deque 라이브러리

1. front에서도 삽입, 삭제가 O(1)에 가능

2. 벡터와 다르게 메모리상 연속된 위치에 존재하지는 않는다.

 

풀이

1. 찾아야 할 target의 위치를 찾는다. O(n)

2. 찾은 위치가 front와 가까운지, back과 가까운지 찾는다. 이때 back은 3번 연산의 수를 한번 더 해줘야 front에서 pop할 수 있으므로, if (log <= DQ.size() /2) 에 등호를 넣도록 한다.

/*boj s4 1021 회전하는 큐*/
#include <iostream>
#include <deque>
#define MAXN 55
using namespace std;

int N, M;

int target[MAXN];
deque<int> DQ;
int answer = 0;

int findTarget(int t)
{
    for (int i = 0; i < DQ.size(); i++)
    {
        if (DQ[i] == t)
            return i;
    }
}
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i < M; i++)
        cin >> target[i];

    for (int i = 1; i <= N; i++)
    {
        DQ.push_back(i);
    }

    for (int m = 0; m < M; m++)
    {
        if (DQ.front() == target[m])
        {
            DQ.pop_front();
        }

        else
        {
            int loc = findTarget(target[m]);

            if (loc <= DQ.size() / 2)
            {
                answer += loc;
                while (loc--)
                {
                    DQ.push_back(DQ.front());
                    DQ.pop_front();
                }
                DQ.pop_front();
            }
            else
            {
                loc = DQ.size() - loc;
                answer += loc;
                while (loc--)
                {
                    DQ.push_front(DQ.back());
                    DQ.pop_back();
                }
                DQ.pop_front();
            }
        }
    }
    cout << answer << '\n';
}