Nodejs Shift vs pop (백준 2164번)

Nodejs의 배열 메서드는 여러가지가 있다. 

 

그중에 대표적으로 shift와 pop이 있다. 

 

최근 알고리즘 문제를 해결하던 중 계속해서 시간 초과에 걸리는 문제가 발생했다. 

문제는 백준 2164번 문제였다. 

 

숫자 N이 주어졌을 때 
숫자 1~N이 적힌 N개의 카드를 순회하며 홀수 회차에는 맨 앞 카드를 제거하고, 짝수 회차에는 맨 앞 카드를 빼서 맨 뒤에 넣는 방식을 반복한 후에 마지막에 남는 카드의 숫자를 구하는 문제였다. 

나는 아무 거리낌 없이 숫자를 배열에 파싱하고 shift와 push을 사용해서 반복문을 수행했는데
계속 시간초과가 걸렸다. 

 

원인은 shift가 O(N)의 시간복잡도를 갖기 때문이었다. 

shift는 맨 앞 요소를 지우고 모든 배열을 한 칸씩 앞으로 옮기기 때문에 O(N)의 시간 복잡도를 갖는다.

 

이 문제를 해결하기 위해서 직접 덱(Deque)을 구현해서 해결할 수 있다. 

 

```

class Deque {
  constructor() {
    this.items = [];
    this.head = 0;
    this.tail = 0;
  }

  push(value) {
    this.items[this.tail++] = value;
  }

  shift() {
    return this.items[this.head++];
  }

  size() {
    return this.tail - this.head;
  }

  front() {
    return this.items[this.head];
  }
}

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim();

const N = Number(input);
const queue = new Deque();

for (let i = 1; i <= N; i++) {
  queue.push(i);
}

while (queue.size() > 1) {
  queue.shift(); // O(1)으로 개선됨
  queue.push(queue.shift());
}

console.log(queue.front());

```