[알고리즘/백준/18258] 큐 2

문제

---

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

18258번: 큐 2

 

풀이

---

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let [n, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");

const N = +n;
const commands = arr.map((com) => com.split(" "));
const answer = [];

class Queue {
  constructor() {
    this.queue = [];
    this.head = 0;
    this.tail = 0;
  }

  push(newElement) {
    this.queue[this.tail] = newElement;
    this.tail += 1;
  }

  pop() {
    if (this.empty()) return -1;

    const front = this.queue[this.head];
    this.head += 1;
    return front;
  }

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

  empty() {
    return this.head === this.tail ? 1 : 0;
  }

  front() {
    return this.empty() ? -1 : this.queue[this.head];
  }

  back() {
    return this.empty() ? -1 : this.queue[this.tail - 1];
  }
}

const q = new Queue();

for (let [com, num] of commands) {
  if (com === "push") q.push(num);
  else answer.push(q[com]());
}

console.log(answer.join("\n"));

 

---

 

시도

 

처음에 pop을 this.queue.shift로 구현했다가 시간 초과가 났다. 생각해보니 shift는 시간 초과의 주범으로 사용하면 안 되는 것이었다.

https://bichoninthefront.tistory.com/25

 

그 다음으로 pop을 아래와 같이 구현했는데 newQueue를 매번 생성해서 메모리 초과가 났다. 

  pop() {
    if (this.empty()) return -1;
    else {
      const [popped, ...newQueue] = this.queue;
      this.queue = newQueue;

      return popped;
    }
  }

 

결국 head, tail을 사용해 큐의 첫 번째, 마지막 인덱스를 지정하는 방식으로 큐를 만들어야 했다. pop하는 경우 this.head 인덱스에 있는 값을 반환하고, this.head를 1 증가해서 첫 번째 요소를 제거한다.