[백준] 18258번: 큐 2 (JavaScript, NodeJS)

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력 1 복사

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

예제 출력 1 복사

1
2
2
0
1
2
-1
0
1
-1
0
3

정답 풀이

const fs = require("fs");

// 백준 제출 할 때 주석 제거
// const readFileSyncAddress = '/dev/stdin';

// VSC 테스트 할 때 주석 제거
const readFileSyncAddress = "input.txt";

const input = fs.readFileSync(readFileSyncAddress).toString().trim().split("\n");

const [n, ...commands] = input;

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

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

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

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

	getSize() {
		return this.size;
	}

	pop() {
		if (this.size > 2) {
			const item = this.head.item;
			const newHead = this.head.next;
			this.head = newHead;
			this.size -= 1;
			return item;
		} else if (this.size === 2) {
			const item = this.head.item;
			const newHead = this.head.next;
			this.head = newHead;
			this.tail = newHead;
			this.size -= 1;
			return item;
		} else if (this.size === 1) {
			const item = this.head.item;
			this.head = null;
			this.tail = null;
			this.size -= 1;
			return item;
		} else {
			return -1;
		}
	}

	empty() {
		return this.size ? 0 : 1;
	}

	front() {
		return this.head ? this.head.item : -1;
	}

	back() {
		return this.tail ? this.tail.item : -1;
	}
}

// 문제 풀이
function solution(n, commands) {
	let answer = '';
	const queue = new Queue();

	for (let i = 0; i < n; i += 1) {
		const command = commands[i].split(' ')[0];

		switch (command) {
			case 'push':
				const pushItem = commands[i].split(' ')[1];
				queue.push(pushItem);
				break;
			case 'pop':
				answer += queue.pop() + ' ';
				break;
			case 'front':
				answer += queue.front() + ' ';
				break;
			case 'back':
				answer += queue.back() + ' ';
				break;
			case 'empty':
				answer += queue.empty() + ' ';
				break;
			case 'size':
				answer += queue.getSize() + ' ';
				break;
			default:
				break;
		}
	}

	return answer.split(' ').join('\n');
}

// 제출
const answer = solution(n, commands);
console.log(answer);

 

자바스크립트 내장 함수 (split, splice, pop, shift)와 같은 함수와

직접 노드를 이용해서 큐를 구현하는 것의 시간 차이를 비교한 포스트가 있다.

 

https://velog.io/@grap3fruit/JS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84-%ED%81%90Queue-%EA%B5%AC%ED%98%84%ED%96%88%EC%9D%84%EB%95%8C-vs-Array-%EB%A9%94%EC%84%9C%EB%93%9Cshift-splice-%EC%82%AC%EC%9A%A9%ED%96%88%EC%9D%84%EB%95%8C-%EC%86%8D%EB%8F%84-%EB%B9%84%EA%B5%90

JS 알고리즘 구현: 큐(Queue) 구현 vs Array 메서드(shift, splice) 사용했을때 속도 비교

 

직접 구현하는 것이 최대 1000배까지 빠르다고하니, 당연히 시간초과가 나는 것이 당연했다.

직접 자료구조를 만드는 연습을 해야할 것 같다.