[바미] 덱 2

문제

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

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = parseInt(input[0], 10);

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

class Deque {
    constructor() {
        this.front = null;
        this.back = null;
        this.size = 0;
    }

    pushFront(value) {
        const node = new Node(value);
        if (this.size === 0) {
            this.front = this.back = node;
        } else {
            node.next = this.front;
            this.front.prev = node;
            this.front = node;
        }
        this.size++;
    }

    pushBack(value) {
        const node = new Node(value);
        if (this.size === 0) {
            this.front = this.back = node;
        } else {
            node.prev = this.back;
            this.back.next = node;
            this.back = node;
        }
        this.size++;
    }

    popFront() {
        if (this.size === 0) return -1;
        const value = this.front.value;
        this.front = this.front.next;
        if (this.front) {
            this.front.prev = null;
        } else {
            this.back = null;
        }
        this.size--;
        return value;
    }

    popBack() {
        if (this.size === 0) return -1;
        const value = this.back.value;
        this.back = this.back.prev;
        if (this.back) {
            this.back.next = null;
        } else {
            this.front = null;
        }
        this.size--;
        return value;
    }

    getSize() {
        return this.size;
    }

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

    frontElement() {
        return this.size === 0 ? -1 : this.front.value;
    }

    backElement() {
        return this.size === 0 ? -1 : this.back.value;
    }
}

const deque = new Deque();
const results = [];

for (let i = 1; i <= N; i++) {
    const command = input[i];
    const parts = command.split(' ');
    const operation = parseInt(parts[0], 10);
    let value;

    switch (operation) {
        case 1:
            value = parseInt(parts[1], 10);
            deque.pushFront(value);
            break;
        case 2:
            value = parseInt(parts[1], 10);
            deque.pushBack(value);
            break;
        case 3:
            results.push(deque.popFront());
            break;
        case 4:
            results.push(deque.popBack());
            break;
        case 5:
            results.push(deque.getSize());
            break;
        case 6:
            results.push(deque.isEmpty());
            break;
        case 7:
            results.push(deque.frontElement());
            break;
        case 8:
            results.push(deque.backElement());
            break;
        default:
            break;
    }
}

console.log(results.join('\n'));

코드 설명

Node 클래스에서 value, next, prev 속성을 가지는 노드를 정의해줍니다. 그리고 연결 리스트의 각 노드는 덱의 요소를 표현합니다.

 

Deque 클래스에서 pushFront, pushBack, popFront, popBack, getSize, isEmpty, frontElement, backElement 메서드를 구현하였습니다.

pushFront, pushBack 메소드에서 덱의 앞과 뒤의 요소를 삽입하고, popFront, popBack 메서드는 덱의 앞과 뒤에서 요소를 제거하고 그 값을 반환하도록 만들었습니다.

 

getSize는 덱의 크기를 반환하는 함수입니다.

isEmpty는 덱이 비어있는지 확인하는 함수입니다.

frontElement, backElement는 덱의 앞과 뒤의 요소 값을 반환해주는 함수입니다.

문제 해설

덱은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조입니다.

 

이 문제는 덱(Deque, Double-ended Queue)을 구현하여 다양한 명령을 처리하는 문제입니다.

주어진 여덟 가지 명령을 효율적으로 처리하기 위해 데이터 구조 선택 시 연결 리스트를 사용하여 덱을 구현한 뒤, 입력된 명령을 파싱하여 각 명령에 맞는 덱 연산을 수행 후 결과를 출력하는 형태로 문제를 해결했습니다.

 

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

각 명령은 상수 시간(O(1))에 처리됩니다. 따라서 N개의 명령이 주어질 때 총 시간 복잡도는 O(N)가 됩니다.

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

덱을 저장하기 위한 공간이 필요하기 때문에 공간 복잡도는 O(N)이 됩니다.