[바미] 큐 2

문제

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

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = parseInt(input[0], 10); // 명령의 수
const commands = input.slice(1); // 명령 리스트

class Queue {
    constructor() {
        this.queue = [];
        this.frontIndex = 0;
        this.backIndex = 0;
    }
    
    push(x) {
        this.queue[this.backIndex++] = x;
    }
    
    pop() {
        if (this.size() === 0) {
            return -1;
        } else {
            return this.queue[this.frontIndex++];
        }
    }
    
    size() {
        return this.backIndex - this.frontIndex;
    }
    
    empty() {
        return this.size() === 0 ? 1 : 0;
    }
    
    front() {
        if (this.size() === 0) {
            return -1;
        } else {
            return this.queue[this.frontIndex];
        }
    }
    
    back() {
        if (this.size() === 0) {
            return -1;
        } else {
            return this.queue[this.backIndex - 1];
        }
    }
}

const queue = new Queue();
const results = [];

for (const command of commands) {
    if (command.startsWith('push')) {
        const [, value] = command.split(' ');
        queue.push(parseInt(value, 10));
    } else if (command === 'pop') {
        results.push(queue.pop());
    } else if (command === 'size') {
        results.push(queue.size());
    } else if (command === 'empty') {
        results.push(queue.empty());
    } else if (command === 'front') {
        results.push(queue.front());
    } else if (command === 'back') {
        results.push(queue.back());
    }
}

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

문제 해설

큐는 FIFO(First-In-First-Out) 원칙을 따르는 자료구조로, 가장 먼저 들어온 요소가 가장 먼저 나가는 구조입니다.

이 문제는 기본적인 큐 자료구조를 구현하고 다양한 명령을 처리하는 문제입니다.

 

주어진 명령을 처리하기 위해 다음과 같은 큐 연산을 구현해야 합니다.

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

Queue라는 클래스안에 큐를 배열로 구현하였고, front와 back 인덱스를 사용하여 큐의 앞과 뒤를 추적하도록 만들었습니다.

 

시간 복잡도

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

 

Queue클래스 안에 있는 명령들은 상수 시간(O(1))에 처리됩니다.

따라서 N개의 명령이 주어질 때 총 시간 복잡도는 O(N)가 됩니다.

공간 복잡도

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

 

큐에 저장되는 정수의 수에 비례하여 메모리가 사용됩니다.

최악의 경우 큐에는 최대 N개의 정수가 저장될 수 있으므로, 공간 복잡도는 O(N)가 됩니다.