[백준,c++] 1021번 - 회전하는 큐

문제

1021번: 회전하는 큐

 

코드

// 22:49~23:22
#include <iostream>
#include <deque>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N,M,ans=0; cin>>N>>M;
    deque<int>dq;
    
    for(int i=1; i<=N; i++) dq.push_back(i);
    
    for(int i=0; i<M; i++){
        int find; cin>>find;
        
        if(find == dq.front()) dq.pop_front();
        else{
            int cnt_second=0, cnt_third=0;
            deque<int> temp_second = dq, temp_third = dq;
            while(true){    // 2번 연산
                if(temp_second.front()==find){
                    temp_second.pop_front();
                    break;
                }
                temp_second.push_back(temp_second.front());
                temp_second.pop_front();
                cnt_second++;
            }
            
            while(true){    //3번 연산
                if(temp_third.front()==find){
                    temp_third.pop_front();
                    break;
                }
                temp_third.push_front(temp_third.back());
                temp_third.pop_back();
                cnt_third++;
            }
            
            if(cnt_second<cnt_third){
                ans += cnt_second;
                dq = temp_second;
            }
            else{
                ans += cnt_third;
                dq = temp_third;
            }
            
        }
        
    }
    cout<<ans;
}

 

풀이(32분)

queue의 front가 뽑아내려고 하는 위치일 때는 바로 뽑아냅니다. 그렇지 않을 경우에는 2번 연산인 왼쪽으로 이동했을 경우와 3번 연산인 오른쪽으로 이동했을 경우의 어느 것이 적은 연산으로 뽑아낼 수 있는지 전부 비교하여 결국 적은 연산으로 총 연산 수에 더해줍니다.