[백준] 1021 회전하는 큐

문제 설명

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

1021번: 회전하는 큐

N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있을 때, 이 큐에서 몇 개의 원소를 뽑아내려고 한다

 

다음 3가지 연산을 수행할 수 있을 때, 원소들을 주어진 순서대로 뽑는데 드는 2번, 3번 연산의 최소값을 구하기

• 첫 번째 원소를 뽑아냄
• 왼쪽으로 한 칸 이동
• 오른쪽으로 한 칸 이동

 

문제 풀이법

양방향 순환 큐를 사용한다고 했으므로 앞, 뒤 모두 pop, push 가능한 deque를 사용한다

 

우선 deque에 값을 집어넣는다

원하는 원소를 입력 받으면서 해당 원소가, dequq에서 몇번째 인덱스에 있는지 확인한다

인덱스와 현재 deque의 사이즈를 기준으로 왼쪽으로 이동시키는것 vs 오른쪽으로 이동시키는 것 둘 중에 어떤것이 가장 효율적인지 따져본다

• idx < d.size() - idx가 참이면 왼쪽으로 한 칸 이동시킨다
• 그렇지 않으면 오른쪽으로 한 칸 이동시킨다

m번만큼 while문을 반복한다

 

소스 코드

#include <iostream>
#include <deque>

using namespace std;


int main()
{
    int cnt = 0;
    deque<int> d;
    
    int n, m;
    cin >> n >> m;
    
    int tmp;
    for (int i = 1; i <= n; i++)
    {
        d.push_back(i);
    }
    
    int idx = 0;
    while (m > 0)
    {
        int tmp;
        cin >> tmp;
        
        for (int i = 0; i < d.size(); i++)
        {
            if (d[i] == tmp)
            {
                idx = i;
                break;
            }
        }
        
        if (idx < d.size() - idx)
        {
            while (1)
            {
                if (d.front() == tmp)
                {
                    d.pop_front();
                    break;
                }
                cnt++;
                d.push_back(d.front());
                d.pop_front();
            }
        }
        else 
        {
            while (1)
            {
                if (d.front() == tmp)
                {
                    d.pop_front();
                    break;
                }
                cnt++;
                d.push_front(d.back());
                d.pop_back();
            }
        }
        
        m--;
    }
    
    printf("%d\n", cnt);
    return 0;
}