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

www.acmicpc.net/problem/1021

1021번: 회전하는 큐

deque을 구현하는 문제였습니다.

 

풀이방법

 1. 뽑을 값을 찾을때까지 왼쪽으로 옮겨봅니다.

 2. 왼쪽으로 옮기는 연산의 개수를 저장합니다.

 3. 해당 개수만큼 원상복귀(우측이동)시켜줍니다.

 4. 다시 뽑을 값을 찾을때까지 오른쪽으로 옮겨봅니다.

 5. 오른쪽으로 옮기는 연산의 개수를 저장합니다.

 6. 해당 개수만큼 원상복귀(좌측이동)시켜줍니다.

 7. 더 적은 연산 개수에 해당하는 방향으로 옮겨주고 값을 pop해줍니다.

Code

#include <bits/stdc++.h>
using namespace std;

deque <int> dq;
int n, m, ans;


void moveLeft(){
    dq.push_back(dq.front());
    dq.pop_front();
}

void moveRight(){
    dq.push_front(dq.back());
    dq.pop_back();
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <=n; i++) dq.push_back(i);
    while(m--){
        int x;
        cin >> x;

        int rightMove = 0;
        int leftMove = 0;

        while(dq.front()!=x){
            moveRight();
            rightMove++;
        }
        
        for(int i = 0; i < rightMove; i++) moveLeft();

        while(dq.front()!=x){
            moveLeft();
            leftMove++;
        }
        
        for(int i = 0; i < leftMove; i++) moveRight();

        if(rightMove < leftMove){
            ans += rightMove;
            while(dq.front()!=x) moveRight();
        }
        else{
            ans += leftMove;
            while(dq.front()!=x) moveLeft();
        }

        dq.pop_front();
    }
    cout << ans << '\n';
}