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

1021번: 회전하는 큐

---

반응형

📌 접근 방법

연산 방법

1. 첫 번째 원소를 삭제한다. 

2. 첫 번째 원소를 맨 뒤에 이동시킨다.

3. 맨 뒤에 있던 원소를 맨 앞으로 이동시킨다.

 

➡ 이 세가지 연산을 이용하여 n 개의 원소 중 입력된 m 개의 원소를 삭제하는 최소 연산 횟수를 구하는 문제 

➡ 연산 횟수에는 두 번째, 세 번째 연산만 포함됨

 

• 맨 끝과 가까운지, 맨 앞과 가까운지 체크해서 가까운 쪽과 관련된 연산을 진행하며 문제를 풀었다.

 

 

 

 

 

✅  Pass Code

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iterator>
#include<map>
#include<set>
#include<unordered_set>
#include <stack>
#include<queue>
#include<deque>

using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N,M,count=0;
    cin>>N>>M;
    deque<int>d;
    for(int i=0; i<N; i++){
        d.push_back(i+1);
    }
    for(int i=0; i<M; i++){
        int x;
        cin>>x;
        int cnt=1;
        for(auto num:d){
            if(x==num){
                break;
            }
            cnt++;
        }
        int left=cnt-1;
        int right=d.size()-cnt+1;
        if(left<right){
            while(true){
                if(d.front()==x){
                    d.pop_front();
                    break;
                }
                d.push_back(d.front());
                d.pop_front();
                count++;
            }
        }
        else{
           while(true){
               if(d.front()==x){
                   d.pop_front();
                   break;
               }
               d.push_front(d.back());
               d.pop_back();
               count++;
           }
        }
    }
    cout<<count<<'\n';

    return 0;
}