백준 01021 - 회전하는 큐

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

1021번: 회전하는 큐

 

고려사항

- 개념은 덱이지만, 큐를 사용하는 것이 간단하다.

- m번 째 수라고 명시하지만, 사실상 1 ~ n 의 수이다. 즉, 특정 수를 뽑았다 해서 몇 번째 수인지 다시 계산 안해도 됨.

- 덱으로 구현해서 앞으로 옮길지, 뒤로 옮기지를 계산하려면 앞 서 뽑아 사라진 수들도 고려해야 하기 때문이다.

- 일반 큐를 사용하여 front == target 이 될 때까지 ++num, push, pop 연산 진행.

- 뽑을 수를 찾았다면, pop을 해주고 num 과 qSize - num  중 작은 값을 구한다.

- num 이 작다면 앞으로 수를 옮기는 게 최소, qSize - num 이 작다면 뒤로 수를 옮기는 게 최소이다.

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    queue<int> q;
    int n, m, target, qSize, num, ans = 0;
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        q.push(i);
    }
    for(int i=0;i<m;++i){
        cin>>target;

        qSize = q.size();
        num = 0;
        while(q.front() != target){
            q.push(q.front());
            q.pop();
            ++num;
        }

        q.pop();
        ans += min(num, qSize-num);
    }

    cout<<ans;
    return 0;
}