[백준] 10866번: 덱 (JavaScript, NodeJS)

문제

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

명령은 총 여덟 가지이다.

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

입력

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

출력

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

예제 입력 1 복사

15
push_back 1
push_front 2
front
back
size
empty
pop_front
pop_back
pop_front
size
empty
pop_back
push_front 3
empty
front

예제 출력 1 복사

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

예제 입력 2 복사

22
front
back
pop_front
pop_back
push_front 1
front
pop_back
push_back 2
back
pop_front
push_front 10
push_front 333
front
back
pop_back
pop_back
push_back 20
push_back 1234
front
back
pop_back
pop_back

예제 출력 2 복사

-1
-1
-1
-1
1
1
2
2
333
10
10
333
20
1234
1234
20

정답 풀이

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;
		this.prev = null;
	}
}

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

	pushFront(item) {
		const newNode = new Node(item);
		if (this.getSize() === 0) {
			this.head = newNode;
			this.tail = newNode;
		} else {
			newNode.next = this.head;
			this.head.prev = newNode;
			this.head = newNode;
		}
		this.size += 1;
	}

	pushBack(item) {
		const newNode = new Node(item);
		if (this.getSize() === 0) {
			this.head = newNode;
			this.tail = newNode;
		} else {
			this.tail.next = newNode;
			newNode.prev = this.tail;
			this.tail = newNode;
		}
		this.size += 1;
	}

	popFront() {
		if (this.getSize() === 0) {
			return -1;
		} else if (this.getSize() === 1) {
			const popedItem = this.head.item;
			this.head = null;
			this.tail = null;
			this.size -= 1;
			return popedItem;
		} else if (this.getSize() === 2) {
			const popedItem = this.head.item;
			this.head = this.head.next;
			this.tail.prev = null;
			this.size -= 1;
			return popedItem;
		} else if (this.getSize() > 2) {
			const popedItem = this.head.item;
			this.head.next.prev = null;
			this.head = this.head.next;
			this.size -= 1;
			return popedItem;
		}
	}

	popBack() {
		if (this.getSize() === 0) {
			return -1;
		} else if (this.getSize() === 1) {
			const popedItem = this.tail.item;
			this.head = null;
			this.tail = null;
			this.size -= 1;
			return popedItem;
		} else if (this.getSize() === 2) {
			const popedItem = this.tail.item;
			this.tail = this.tail.prev;
			this.head.next = null;
			this.size -= 1;
			return popedItem;
		} else if (this.getSize() > 2) {
			const popedItem = this.tail.item;
			this.tail.prev.next = null;
			this.tail = this.tail.prev;
			this.size -= 1;
			return popedItem;
		}
	}

	getSize() {
		return this.size;
	}

	isEmpty() {
		return this.getSize() ? 0 : 1;
	}

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

	getBack() {
		return this.getSize() ? this.tail.item : -1
	}
}

// 문제 풀이
function solution(n, commands) {
	const deque = new Deque();
	let answer = '';
	for (let i = 0; i < commands.length; i += 1) {
		const [command, item] = commands[i].split(' ');
		switch (command) {
			case 'push_front': deque.pushFront(item); break;
			case 'push_back': deque.pushBack(item); break;
			case 'pop_front': answer += deque.popFront() + ' '; break;
			case 'pop_back': answer += deque.popBack() + ' '; break;
			case 'size': answer += deque.getSize() + ' '; break;
			case 'empty': answer += deque.isEmpty() + ' '; break;
			case 'front': answer += deque.getFront() + ' '; break;
			case 'back': answer += deque.getBack() + ' '; break;
			default: break;
		}
	}

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

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

 

Deque를 자바스크립트로 구현하는 문제이다.

Deque는 양쪽에 포인터를 두어서 끝에서도 추가, 삭제를 할 수 있고

앞에서도 추가, 삭제를 할 수 있는 자료구조이다.

 

그래서 각 노드마다 next 노드 포인터를 두는 게 아니라 prev 포인터까지 둬서

구현을 해야한다.