[BOJ] 1021번 회전하는 큐

BOJ 1021번 회전하는 큐

덱 사용

풀이

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

int main() {
  int N,M,x,answer=0, left, right;
  deque<int>::iterator it;
  cin>>N>>M;

  deque<int> q(N);
  
  for(int i=0;i<N;i++){
    q[i]=i+1;
  }

  for(int i=0;i<M;i++){
    cin >> x;

    it = find(q.begin(), q.end(), x);
    left = it-q.begin();
    right = q.end() - it -1;

    if(left <= right) {
      answer += left;
      for(int j=0;j<left;j++){
        q.push_back(q.front());
        q.pop_front();
      }
      q.pop_front();

    } else {
      answer += right+1;
      for(int j=0;j<right;j++){
        q.push_front(q.back());
        q.pop_back();
      }
      q.pop_back();
      
    }
  }

  cout<<answer;
  
  return 0;
}

시간복잡도

최악의 경우 N/2 번씩 M번 반복하고, find() 함수의 경우 O(N)이므로 오... O(N^2)...