(C++) 백준 1021번 - 회전하는 큐

문제 링크 : https://www.acmicpc.net/problem/1021

1021번: 회전하는 큐

풀이

덱의 push와 pop을 사용하여 회전하는 큐를 어렵지 않게 구현할 수 있다.

다만 왼쪽으로 가는 것과 오른쪽으로 가는 것을 선택하는 알고리즘을 짜는 것에 고민을 많이 했는데, 단순하게 순회하며 어디가 더 가까운지 세는 것으로도 해결이 된다.

#include <iostream>
#include <deque>

using namespace std;

deque<int> D;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  
    
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        D.push_back(i);
    }
    int cnt = 0;
    while(m--){
        int i;
        cin >> i;
        int left, right;
        
        // 왼쪽으로 가는 것이 빠른지, 오른쪽으로 가는 것이 빠른지 체크
        for(int index = 0; index < D.size(); index++){
            if(D[index] == i){
                left = index;
                right = D.size()-index;
                break;
            }
        }
        if(left >= right){ // 오른쪽으로 이동 (3번 연산)
            while(1){
                if(i == D.front()){
                    D.pop_front();
                    break;
                }
                int tmp;
                tmp = D.back();
                D.pop_back();
                D.push_front(tmp);
                cnt++;
            }
        }else{ // 왼쪽으로 이동 (2번 연산)
            while(1){
                if(i == D.front()){
                    D.pop_front();
                    break;
                }
                int tmp;
                tmp = D.front();
                D.pop_front();
                D.push_back(tmp);
                cnt++;
            }            
        }
    }
    cout << cnt;
}