(BOJ) 1021 풀이

#include<bits/stdc++.h>

using namespace std;
deque<int> DQ;
int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M,ans=0;
    cin >> N >> M;
    for(int i=1;i<=N;i++){
        DQ.push_back(i);
    }
    for(int i=1;i<=M;i++){
        int n;
        cin >> n;
        int idx=find(DQ.begin(),DQ.end(),n)-DQ.begin();
        // cout << "idx : " << idx << '\\n';
        while(DQ.front()!=n){
            // cout << DQ.front() << '\\n';
            ans++;
            if(DQ.size()/2<idx){
                DQ.push_front(DQ.back());
                DQ.pop_back();
            }else{
                DQ.push_back(DQ.front());
                DQ.pop_front();
            }
        }
        // cout << "ans : " << DQ.front() << '\\n';
        DQ.pop_front();
    }
    cout << ans;

}

덱 자료구조를 이용해 푸는 문제였다.

N 개의 자료들을 각각 찾기위해 덱을 오른쪽 or 왼쪽으로 쉬프트한 뒤 pop 한다.

pop 횟수를 제외하고 돌리는 횟수만 출력하면 된다.

 

덱에 1~9 의 원소가 순서대로 나열되어있을 때,

1부터 시작하는데, 9를 찾기 위해서는 오른쪽으로 한 번 돌리면

9가 첫 번째로 오는 양방향인 점을 알고 있어야하고,

 

오른쪽으로 돌릴지 왼쪽으로 돌릴지 결정하는 방법은 다음과 같다.

인덱스로 접근할 수 있는 덱은 find 로 값의 위치를 찾을 수 있다.

그래서 DQ.size() / 2 보다 뒤에있는 값은 오른쪽으로 돌려서 찾으면 된다.

DQ 의 size 는 값을 찾을 때마다 변하기 때문에 N이 아니라 DQ.size() 으로 써야한다.