[백준] 회전하는 큐

설명

자료구조 Deque를 사용해서 푸는 문제
JS의 경우 덱이 없어서 완벽한 덱은 아니지만 문제에서 주어진 N은 50보다 작거나 같은 자연수라는 조건 때문에 Array를 extends하여 심플하게 구현했다.
그리고 필요한 rotate 함수를 파이썬의 덱처럼 멤버변수로 추가하여 문제를 풀었다.

C++의 경우 rotate 함수가 없는 것과 index를 찾기 위해 일일히 덱을 순회한 점이 불편했다...

Node.js 풀이

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
// test
const input = `10 10
1 6 3 2 7 9 8 4 10 5`
  .trim()
  .split('\n');
const [N, M] = input[0].split(' ').map(Number);
const orders = input[1].split(' ').map(Number);

class Deque extends Array {
  front() {
    return this[0];
  }
  back() {
    return this[this.length - 1];
  }
  popLeft() {
    return this.shift();
  }
  rotate(idx) {
    if (idx > 0) {
      while (idx--) this.unshift(this.pop());
    } else {
      while (idx++) this.push(this.shift());
    }
  }
}

const solution = (N, M, orders) => {
  const deque = new Deque();
  let count = 0;
  for (let i = 1; i <= N; i++) deque.push(i);
  orders.forEach((order) => {
    const idx = deque.indexOf(order);
    if (idx === 0) deque.popLeft();
    else {
      if (idx <= Math.floor(deque.length / 2)) {
        deque.rotate(-idx);
        deque.popLeft();
        count += idx;
      } else {
        deque.rotate(deque.length - idx);
        count += deque.length - idx;
        deque.popLeft();
      }
    }
  });
  return count;
};

console.log(solution(N, M, orders));

C++ 풀이

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N, M;
    cin >> N >> M;
    deque<int> DQ;
    for (int i=1; i<=N; i++) DQ.push_back(i);
    int cnt = 0;
    int left, right;
    for (int i=0; i<M; i++) {
        int num; cin >> num;
        for (int j=0; j<DQ.size(); j++) {
            if (DQ[j] == num) {
                left = j;
                right = DQ.size() - left;
                break;
            }
        }
        
        if (left < right) {
            cnt += left; 
            while(left--) {
                DQ.push_back(DQ.front());
                DQ.pop_front();
            }
            DQ.pop_front();
            
        } else {
            cnt += right; 
            while(right--) {
                DQ.push_front(DQ.back());
                DQ.pop_back();
            }
            DQ.pop_front();
        }
    }
    cout << cnt << '\n';
    return 0;
}