Node.js)백준 12852번: 1로 만들기 2

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

12852번: 1로 만들기 2

class Node {
  constructor(item) {
    this.item = item;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(item) {
    const node = new Node(item)
    if (this.head == null) {
      this.head = node;
    } else {
      this.tail.next = node;
    }

    this.tail = node;
    this.length += 1;
  }

  pop() {
    const popItem = this.head;
    this.head = this.head.next;
    this.length -= 1;
    return popItem.item;
  }

}

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

let q = new Queue();
let answer = input;
let temp = [];
let visited = new Array(input + 1).fill(input)
q.push([input])
while (q.length > 0) {
  const arr = q.pop();
  const L = arr.length;
  if (L > answer) continue;
  if (arr[L - 1] == 1) {
    answer = L;
    temp = arr;
    break;
  } else {
    const last = arr[L - 1];
    if (last % 3 == 0 && visited[last / 3] > L) {
      visited[last / 3] = L
      q.push([...arr, last / 3]);
    }
    if (last % 2 == 0 && visited[last / 2] > L) {
      visited[last / 2] = L
      q.push([...arr, last / 2]);
    }
    if (last - 1 > 0 && visited[last - 1] > L) {
      visited[last - 1] = L
      q.push([...arr, last - 1])
    }
  }
}

console.log(answer - 1)
console.log(temp.join(' '))