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

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

1021번: 회전하는 큐

이 문제는 처음과 끝이 연결되어 있는 큐가 있을 때 큐의 처음으로 이동시켜서 뽑아야 하는 원소들을 뽑아야 하는데

왼쪽으로 전체 한 칸 미는 연산과(처음의 원소는 끝으로) 오른쪽으로 전체 한 칸 미는 연산을(끝의 원소는 처음으로) 최소한의 횟수로 해서 뽑는 문제이다.

 

문제를 푸는 방법은 일단 deque를 하나 선언해주고 회전하는 큐의 크기만큼 자연수를 넣어 deque를 초기화시켜준다.

그 뒤 뽑아내려고 하는 원소의 위치를 먼저 파악한 뒤 (deque를 자연수로 초기화해놨기 때문에 deque안에 뽑아내려는 원소와 같은 원소를 찾으면 된다.)

이 원소가 왼쪽으로 이동시켜서 뽑을 때 더 조금 연산하는지 오른쪽으로 이동시켜서 뽑을 때 더 조금 연산하는지 파악한 뒤 더 조금 연산하는 방향으로 연산 횟수를 누적해주며 연산하면 된다.

 

리스트를 이용해 deque를 구현해도 되지만 stl을 연습해보는 겸 deque stl을 사용하여 문제를 풀었다.

#include <iostream>
#include <cstdio>
#include <deque>
using namespace std;

int main() {
    int N, M, cnt=0;
    scanf("%d %d",&N,&M);
    deque<int> dq;
    
    for(int i=1;i<=N;i++) {
        dq.push_back(i);
    }
    
    for(int i=0;i<M;i++) {
        int num;
        scanf("%d",&num);
        
        if(dq.front()==num) {
            dq.pop_front();
        }
        else {
            int target;
            for(int j=0;j<dq.size();j++) {
                if(dq[j]==num) {
                    target = j;
                }
            }
            if(dq.size()-target <= target) {
                for(int k=0;k<dq.size()-target;k++) {
                    dq.push_front(dq.back());
                    dq.pop_back();
                    cnt++;
                }
                dq.pop_front();
            }
            else {
                for(int k=0;k<target;k++) {
                    dq.push_back(dq.front());
                    dq.pop_front();
                    cnt++;
                }
                dq.pop_front();
            }
        }
    }
    
    printf("%d",cnt);
    
    return 0;
}