BOJ 1021 c++ 회전하는 큐

BOJ 1021 c++ 회전하는 큐

백준 1021 cpp 회전하는 큐

 

정답률이 50%에 가까운데도 못 풀어서 자존심에 스크래치가 났던 문제.

auto e 로 duque 을 순환할 수 있다는 것만 미리 알았어도 시간 뺏기지 않았을 문제..

 

덱을 이용하면 쉽게 풀 수 있다.

target의 인덱스가 (덱의 사이즈 / 2) 보다 큰지 조사한 후에 크다면 오른쪽에서 왼쪽으로 넘기고, 아니면 왼쪽에서 오른쪽으로 넘긴다.

 

#include <bits/stdc++.h>
using namespace std;

int n, ea;
deque<int> D;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> ea;
    for (int i = 1; i <= n; i++)
        D.push_back(i);

    int ans = 0;
    while (ea--)
    {
        int target;
        cin >> target;

        if (D.front() == target)
        {
            D.pop_front();
        }
        else
        {
            int size = D.size() / 2;
            if (D.size() % 2 == 1)
            {
                size += 1;
            }

            int idx = 0;
            for (auto e: D)
            {
                if (e == target)
                {
                    idx++;
                    break;
                }
                idx++;
            }
            if (idx <= size)
            {
                while (D.front() != target)
                {
                    int temp;
                    temp = D.front();
                    D.push_back(temp);
                    D.pop_front();
                    ans++;
                }
            }
            else 
            {
                while (D.front() != target)
                {
                    int temp;
                    temp = D.back();
                    D.push_front(temp);
                    D.pop_back();
                    ans++;
                }
            }
            D.pop_front();
        }
    }
    cout << ans;
}