문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
문제 출처 : https://www.acmicpc.net/problem/18258
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
첫 시도
const fs = require("fs");
let [count,...rest] = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const queue = [];
const result = [];
const queueActions = {
push : (x) => queue.push(x),
pop : () => queue.length === 0 ? result.push(-1) : result.push(queue.shift()),
size : () => result.push(queue.length),
empty : () => queue.length === 0 ? result.push(1) : result.push(0),
front : () => queue.length === 0 ? result.push(-1) : result.push(queue[0]),
back : () => queue.length === 0 ? result.push(-1) : result.push(queue[queue.length-1]),
}
rest.forEach((el) => {
const [method, num] = el.split(" ");
queueActions[method](num);
})
console.log(result.join("\n"));맞게는 푼 것 같지만 시간 초과 오류가 났다. 아마 shift() 때문에 최악의 경우 O(N^2)의 상황이 생기기에 그런 것 같다.
두번째 시도
const fs = require("fs");
let [count,...rest] = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
class Queue {
constructor() {
this.storage = {};
this.first = 0;
this.last = 0;
}
size() {
if (this.storage[this.last] === undefined) {
return 0;
} else {
return this.last - this.first + 1;
}
}
empty() {
if (this.storage[this.last] === undefined ) {
return 1
} else {
return 0
}
}
push(value) {
if (this.size() === 0) {
this.storage['0'] = value;
} else {
this.last += 1;
this.storage[this.last] = value;
}
}
pop() {
if(this.storage[this.last] === undefined) {
return -1;
}
let temp;
if (this.first === this.last) {
temp = this.storage[this.first];
delete this.storage[this.first];
this.first = 0;
this.last = 0;
} else {
temp = this.storage[this.first];
delete this.storage[this.first];
this.first += 1;
}
return temp;
}
front() {
if(this.storage[this.last] === undefined) {
return -1
} else {
return this.storage[this.first]
}
}
back() {
if(this.storage[this.last] === undefined) {
return -1
} else {
return this.storage[this.last]
}
}
}
const queue = new Queue();
const result = [];
rest.forEach((el) => {
const [method, num] = el.split(" ");
if(method !== "push") {
result.push(queue[method]());
} else {
queue[method](num);
}
})
console.log(result.join("\n"));다른 벨로거분의 글을 참고하여 class로 queue를 만들었다. object의 key를 인덱스로 활용하여서, pop()을 하더라도 해당 key만 지우고 pointer의 값을 1 증가하는 형식으로 고려했다. 정답은 되었지만 생각보다 시간 효율이 좀 나오지 않았다. 그래도 queue 자체를 구현해본 것에 만족했다.
세 번째 시도(queue를 리스트로?)
const fs = require("fs");
let [count,...rest] = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
class Queue {
constructor() {
this.storage = [];
this.first = 0;
}
size() {
return this.storage.length - this.first;
}
empty() {
return this.size() === 0 ? 1 : 0;
}
push(value) {
this.storage.push(value);
}
pop() {
if(this.size() === 0) {
return -1;
} else {
this.first++;
return this.storage[this.first-1];
}
}
front() {
if(this.size() === 0) {
return -1
} else {
return this.storage[this.first];
}
}
back() {
if(this.size() === 0) {
return -1
} else {
return this.storage[this.storage.length -1];
}
}
}
const queue = new Queue();
const result = [];
rest.forEach((el) => {
const [method, num] = el.split(" ");
if(method !== "push") {
result.push(queue[method]());
} else {
queue[method](num);
}
})
console.log(result.join("\n"));포인터에서 영감을 받아 리스트로 구현해본 queue이다. 하지만 리스트의 경우엔 pointer로 유지하면서 데이터를 삭제할 수 없기 때문에, pop을 하더라도 사실상 데이터는 유지되면서 인덱스만 이동하는 구조이다. object를 삭제하고 다시 재할당하는 로직이 빠지면서 100ms 가량 빨라졌지만 반대로 메모리 사용량은 커졌다.
다른 사람들도 다 비슷한 로직으로 했거나, class를 이용하지 않고 생으로 개발한 상태인 것 같다.
회고
- js로 앞에서 인덱스를 빼야 할 일이 있는 경우엔 다음과 같이 직접
queue로 구현하자. 괜히shift()썻다가O(N)나오기 보단, 단순히 해당 인덱스의 값만 가져오는O(1)효율을 내기 때문이다!
