자바스크립트로 알고리즘 정리하기 #2 Queue 구현 및 관련 문제풀이

자바스크립트로 알고리즘 정리하기 #2 Queue 구현 및 관련 문제풀이

Queue 개념

• 한 쪽 끝에서 자료를 넣고 다른 한 쪽 끝에서만 자료를 뺄 수 있는 구조

• 먼저 넣은 것이 가장 먼저 나옴(FIFO)

• push() / enqueue() : 큐에 자료를 넣는다.

• pop() / dequeue() : 큐의 자료를 뺀다

• front() : 큐의 가장 앞에 있는 자료를 보는 연산

• back() : 큐의 가장 뒤에 있는 자료를 보는 연산

• isEmpty() : 큐가 비어있는지 아닌지 알아보는 연산

• size() : 큐에 저장되어 있는 자료의 개수를 알아보는 연산

Queue의 용례

• BFS 알고리즘에서 많이 사용함

Queue의 구현

• 배열 하나로 구현 가능함

class Queue {
  constructor() {
    this.data = [];
    this.rear = 0;
    this.size = 10;
  }

  enqueue(element) {
    if (this.rear < this.size) {
      this.data[this.rear] = element;
      this.rear = this.rear + 1;
      return true;
    }
    // if there is no place to insert data
    return false;
  }

  dequeue() {
    if (this.isEmpty() === false) {
      this.rear = this.rear - 1;
      return this.data.shift();
    }
  }

  length() {
    return this.rear;
  }

  isEmpty() {
    return this.rear === 0;
  }

  getFront() {
    if (this.isEmpty() === false) {
      return this.data[0];
    }
  }

  getLast() {
    if (this.isEmpty() === false) {
      return this.data[this.rear - 1];
    }
  }

  print() {
    for (let i = 0; i < this.rear; i++) {
      console.log(this.data[i]);
    }
  }
}

let queue = new Queue();

queue.enqueue("1");
queue.enqueue("2");
queue.enqueue("3");
queue.enqueue("4");
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());

// by FIFO this output must be "1","2","3","4"

구현 참고

boj 10845

문제 링크

위에서 구현한 자료구조 Queue에서 문자열별로 루틴을 나누어주기만 하면 된다.

class Queue {
  constructor() {
    this.data = [];
    this.rear = 0;
    this.size = 10000;
  }

  enqueue(element) {
    if (this.rear < this.size) {
      this.data[this.rear] = element;
      this.rear = this.rear + 1;
      return true;
    }
    // if there is no place to insert data
    return false;
  }

  dequeue() {
    if (this.isEmpty() === false) {
      this.rear = this.rear - 1;
      return this.data.shift();
    }

    return -1;
  }

  length() {
    return this.rear;
  }

  isEmpty() {
    return this.rear === 0;
  }

  getFront() {
    if (this.isEmpty() === false) {
      return this.data[0];
    }

    return -1;
  }

  getLast() {
    if (this.isEmpty() === false) {
      return this.data[this.rear - 1];
    }

    return -1;
  }

  print() {
    for (let i = 0; i < this.rear; i++) {
      console.log(this.data[i]);
    }
  }
}

let queue = new Queue();

let solution = (inputLines) => {
  let n = inputLines.shift();
  let answer = "";

  for (let i = 0; i < n; i++) {
    let [command, arg] = inputLines[i].split(" ");

    if (command === "push") {
      queue.enqueue(+arg);
    }

    if (command === "pop") {
      answer += queue.dequeue() + "\n";
    }

    if (command === "size") {
      answer += queue.length() + "\n";
    }

    if (command === "empty") {
      answer += (queue.isEmpty() ? 1 : 0) + "\n";
    }

    if (command === "front") {
      answer += queue.getFront() + "\n";
    }

    if (command === "back") {
      answer += queue.getLast() + "\n";
    }
  }

  return answer;
};

/*
let example1 =
  "15\npush 1\npush 2\nfront\nback\nsize\nempty\npop\npop\npop\nsize\nempty\npop\npush 3\nempty\nfront";
*/

(function () {
  let inputLines = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .split("\n");

  console.log(solution(inputLines));
})();

boj 1158

문제 링크

Queue 를 이용한 직관적 풀이

queue를 이용해서 문제를 직관적으로 풀면 1명1명씩 k-1명을 뒤로 밀고 k번째를 제거하는 방식으로 풀면 된다.

단, 배열에서 여러 원소들의 위치를 매번 바꾸거나 새로 구성하는 것은 많은 비용을 요구하기 때문에 속도 측면에서는 느릴 수 있다.

class Queue {
  constructor() {
    this.data = [];
    this.rear = 0;
    this.size = 100000;
  }

  enqueue(element) {
    if (this.rear < this.size) {
      this.data[this.rear] = element;
      this.rear = this.rear + 1;
      return true;
    }
    // if there is no place to insert data
    return false;
  }

  dequeue() {
    if (this.isEmpty() === false) {
      this.rear = this.rear - 1;
      return this.data.shift();
    }

    return false;
  }

  length() {
    return this.rear;
  }

  isEmpty() {
    return this.rear === 0;
  }

  getFront() {
    if (this.isEmpty() === false) {
      return this.data[0];
    }

    return false;
  }

  getLast() {
    if (this.isEmpty() === false) {
      return this.data[this.rear - 1];
    }

    return false;
  }

  print() {
    for (let i = 0; i < this.rear; i++) {
      console.log(this.data[i]);
    }
  }
}

let solution = (inputLines) => {
  let queue = new Queue();
  let answer = [];
  let [n, k] = inputLines.split(" ").map((e) => +e);

  for (let i = 1; i <= n; i++) {
    queue.enqueue(i);
  }

  while (!queue.isEmpty()) {
    for (let i = 1; i < k; i++) {
      queue.enqueue(queue.dequeue());
    }
    answer.push(queue.dequeue());
  }

  return "<" + answer.join(", ") + ">";
};

(function () {
  let inputLines = require("fs").readFileSync("/dev/stdin").toString();

  console.log(solution(inputLines));
})();

Queue 자료구조 안쓰고 풀기

아래 방법은 Queue 자료구조를 쓰지 않는 방법이다.

어떻게 푸냐하면 문제에서 사람들이 원의 형태로 모여있다고 했고 k번째 사람이 하나씩 지워져가는 것이기 때문에 원의 형태라 가정하고 k번째를 지우면 된다.

원의 형태처럼 k번째 사람을 지우기 위해 %연산을 이용하면 된다.

let solution = (inputLines) => {
  let [n, k] = inputLines.split(" ");
  let arr = Array(+n)
    .fill(0)
    .map((e, i) => i + 1);
  let answer = [];
  let idx = 0;

  while (arr.length !== 0) {
    idx += k - 1;
    idx %= arr.length;
    answer.push(arr.splice(idx, 1)[0]);
  }

  return "<" + answer.join(", ") + ">";
};

(function () {
  let inputLines = require("fs").readFileSync("/dev/stdin").toString();
  console.log(solution(inputLines));
})();