문제풀이
이 문제를 풀이하는데 있어서 중요한 것은 자바스크립트로 직접 큐를 구현하는 것이었다.
보통 배열을 사용해서 큐처럼 사용을 하는데 배열의 shift() 메소드의 시간복잡도가 O(n)이기 때문에 시간초과가 발생한다. 때문에 이중연결리스트로 큐를 구현해서 삽입, 삭제의 시간복잡도를 O(1)로 만들 필요가 있다.
내가 구현(?)하고 다른 사람의 코드를 참고하며 만든 이중 연결리스트
class Node {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor(arr) {
this.head = null;
this.tail = null;
this.length = 0;
}
unshift(data) {
const node = new Node(data);
if (this.head === null) {
this.head = node;
this.tail = node;
} else {
node.next = this.head;
this.head.prev = node;
this.head = node;
}
this.length++;
}
push(data) {
const node = new Node(data);
if (this.tail === null) {
this.tail = node;
this.head = node;
} else {
node.prev = this.tail;
this.tail.next = node;
this.tail = node;
}
this.length++;
}
shift() {
if (this.head === null) {
return;
}
const head = this.head;
if (this.length === 1) {
this.head = null;
this.tail = null;
this.length--;
} else {
this.head = this.head.next;
this.head.prev = null;
this.length--;
}
return head;
}
pop() {
if (this.tail === null) {
return;
}
const tail = this.tail;
this.tail = this.tail.prev;
this.tail.next = null;
this.length--;
return tail;
}
insert(data, index) {
if (index < 0 || index > this.length) {
console.log("invaild index");
return;
}
if (index === 0) {
this.unshift(data);
return;
}
if (index === this.length) {
this.push(data);
return;
}
const node = new Node(data);
let pointer = 0;
let current = this.head;
let before;
while (pointer < index) {
pointer++;
before = current;
current = current.next;
}
node.next = current;
node.prev = before;
before.next = node;
current.prev = node;
this.length++;
}
delete(index) {
if (index < 0 || index > this.length - 1) {
console.log("invalid index");
return;
}
if (index === 0) {
this.head = this.head.next;
this.head.prev = null;
this.length--;
return;
}
if (index === this.length - 1) {
this.tail = this.tail.prev;
this.tail.next = null;
this.length--;
return;
}
let current = this.head;
let before;
let pointer = 0;
while (pointer < index) {
pointer++;
before = current;
current = current.next;
}
before.next = current.next;
before.next.prev = before;
this.length--;
}
print() {
const list = [];
let current = this.head;
while (current) {
list.push({
data: current.data,
prev: current.prev?.data,
next: current.next?.data,
});
current = current.next;
}
console.log(list);
}
}그리고 제출한 코드
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [N, ...input] = fs.readFileSync(filePath).toString().trim().split("\n");
const arr = input.map((v) => v.split(" "));
class Node {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor(arr) {
this.head = null;
this.tail = null;
this.length = 0;
}
unshift(data) {
const node = new Node(data);
if (this.head === null) {
this.head = node;
this.tail = node;
} else {
node.next = this.head;
this.head.prev = node;
this.head = node;
}
this.length++;
}
push(data) {
const node = new Node(data);
if (this.tail === null) {
this.tail = node;
this.head = node;
} else {
node.prev = this.tail;
this.tail.next = node;
this.tail = node;
}
this.length++;
}
shift() {
if (this.head === null) {
return;
}
const head = this.head;
if (this.length === 1) {
this.head = null;
this.tail = null;
this.length--;
} else {
this.head = this.head.next;
this.head.prev = null;
this.length--;
}
return head;
}
pop() {
if (this.tail === null) {
return;
}
const tail = this.tail;
this.tail = this.tail.prev;
this.tail.next = null;
this.length--;
return tail;
}
insert(data, index) {
if (index < 0 || index > this.length) {
console.log("invaild index");
return;
}
if (index === 0) {
this.unshift(data);
return;
}
if (index === this.length) {
this.push(data);
return;
}
const node = new Node(data);
let pointer = 0;
let current = this.head;
let before;
while (pointer < index) {
pointer++;
before = current;
current = current.next;
}
node.next = current;
node.prev = before;
before.next = node;
current.prev = node;
this.length++;
}
delete(index) {
if (index < 0 || index > this.length - 1) {
console.log("invalid index");
return;
}
if (index === 0) {
this.head = this.head.next;
this.head.prev = null;
this.length--;
return;
}
if (index === this.length - 1) {
this.tail = this.tail.prev;
this.tail.next = null;
this.length--;
return;
}
let current = this.head;
let before;
let pointer = 0;
while (pointer < index) {
pointer++;
before = current;
current = current.next;
}
before.next = current.next;
before.next.prev = before;
this.length--;
}
print() {
const list = [];
let current = this.head;
while (current) {
list.push({
data: current.data,
prev: current.prev?.data,
next: current.next?.data,
});
current = current.next;
}
console.log(list);
}
}
let answer = [];
const queue = new DoublyLinkedList();
for (let [command, X] of arr) {
switch (command) {
case "push":
queue.push(X);
break;
case "pop":
if (queue.length > 0) {
const head = queue.shift();
answer.push(head.data);
} else {
answer.push(-1);
}
break;
case "size":
answer.push(queue.length);
break;
case "empty":
if (queue.length > 0) {
answer.push(0);
} else {
answer.push(1);
}
break;
case "front":
if (queue.length > 0 && queue.head) {
answer.push(queue.head.data);
} else {
answer.push(-1);
}
break;
case "back":
if (queue.length > 0 && queue.tail) {
answer.push(queue.tail.data);
} else {
answer.push(-1);
}
break;
default:
break;
}
}
console.log(answer.join("\n"));