[BOJ / C++] 회전하는 큐(1021)

문제

회전하는 큐 : 문제 링크

문제 분석

• 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있고, 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

  1. 첫 번째 원소를 뽑아낸다. (a1,...,ak -> a2,...,ak)
  2. 왼쪽으로 한 칸 이동시킨다. (a1,...,ak -> a2,...,ak,a1)
  3. 오른쪽으로 한 칸 이동시킨다. (a1,...,ak -> ak,a1,...,ak-1)

• 큐에 처음에 포함되어 있던 수 N과 뽑아내려고 하는 원소의 위치(가장 처음 큐에서의 위치)가 주어진다. 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2,3번 연산의 최솟값을 출력

• int 변수 N, M에 각각 값을 입력받고, M크기의 int형 vector idx 및 int형 deque dq를 초기화 했다. for loop를 통해 dq에 1부터 N까지 저장하고, idx에는 뽑아내려는 원소의 위치를 입력받는다. 두번째 for loop에서 int 변수 n에 idx에 저장된 원소를 순서대로 저장하고, find() 함수로 그것의 위치를 찾고 pos에 저장한다. pos가 dq의 크기보다 작거나 같다면 즉 절반보다 앞쪽이라면 2번 연산을, 뒤쪽이라면 3번 연산을 수행

• 2,3번 연산을 수행할 때마다 count를 1씩 늘려주었고 마지막에 그것을 출력

덱(deque)
double-ended queue의 약자이며 덱이라고 부른다.

template<typename _Ty, typename _Alloc = allocator<_Ty>> class deque;

이름에서 알 수 있다싶이 양방향 큐 자료구조인데 항목열 중간에 대한 룩업도 제공하기 때문에 벡터와 매우 유사하다.

• vector와의 차이점
  1) deque은 연속된 메모리에 항목을 저장할 필요가 없다.
  2) deque은 앞쪽과 뒤쪽 모두에서 상수 시간의 삽입/삭제 성능을 가진다.
  3) deque은 vector에 없는 push_front, pop_front 메서드가 제공된다.
  4) deque은 vector의 reserve, capacity 메서드처럼 내부메모리 관리 기능을 노출하지 않는다.

풀이

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

int main()
{
    int N, M, temp;
    int count = 0;
    
    cin >> N >> M;
    deque<int> dq;
    deque<int> idx(M);
    for(int i = 1; i <= N; i++)
        dq.push_back(i);
    for(int j = 0; j < idx.size(); j++) {
        cin >> idx[j];
        int n = idx[j];
        deque<int>::iterator it = find(dq.begin(), dq.end(), n);
        int pos = distance(dq.begin(), it);
        if (pos <= dq.size() / 2) {
            while(dq.front() != n) {
                temp = dq.front();
                dq.pop_front();
                dq.push_back(temp);
                count++;
            }
        }
        else {
            while(dq.front() != n) {
                temp = dq.back();
                dq.pop_back();
                dq.push_front(temp);
                count++;
            }
        }
        dq.pop_front();
    }
    cout << count;
    return 0;
}