greentea31's Note

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

풀이 과정

양방향 순환 큐를 회전시키면서 원하는 수를 모두 뽑아내려면 필요한 최소 회전 횟수를 구하는 문제이다.

덱을 회전시키면서 원하는 숫자를 모두 뽑아가면서 회전을 몇번 시켰는지 구하면 된다. 근데 원하는 수가 큐의 앞에 있는 수를 뒤로 넘겨가면서 찾아야 빠른지, 뒤에 있는 수를 앞으로 넘겨가면서 빠른지 어떻게 구분이 가능할까?

판단하려면 일단 찾고자 하는 수가 덱의 몇번째 index에 있는지 알아야 한다. find(DQ.begin(), DQ.end(), num)으로 num이 존재하는 위치의 주소값을 받아오고 거기서 DQ.begin()을 빼서 index를 구해주자.

여기서 구한 index의 2배가 덱의 사이즈보다 작으면 앞에 있는 수를 뒤로 넘기는게 빠르고, 크면 뒤에 있는 수를 앞으로 넘기는게 빠를 것이다. 예시를 들면 0 1 2 3 4 5 6 7 8 9에서 라는 덱에서 4는 4번째 index에 있으므로 4*2 < 10 이므로 앞에서 찾는게 빠를 것이라고 생각할 수 있다.

5는 5번째 index에 있는데, 5*2 < 10이다. index의 2배가 덱의 사이즈랑 같은 경우에는 앞에서 찾던 뒤에서 찾던 횟수의 차이가 없으나, 뒤에서 찾도록 구현하였다.

소스 코드

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    deque<int> DQ;

    int N;
    cin >> N;

    for (int i = 1 ; i <= N; i++) {
        DQ.push_back(i);
    }

    int M;
    cin >> M;

    int answer = 0;

    while(M--) {
        int num;
        cin >> num;
        int idx = find(DQ.begin(), DQ.end(), num) - DQ.begin(); // num의 index값
        while (DQ.front() != num) {
            if (2*idx < DQ.size()) {
                DQ.push_back(DQ.front());
                DQ.pop_front();
            } else {
                DQ.push_front(DQ.back());
                DQ.pop_back();
            }
            answer++;
        }
        DQ.pop_front();
    }

    cout << answer;

    return 0;
}