[백준/JS] 18258번_큐2

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

18258번: 큐 2

---

 

[ 문제 풀이 과정 ]

아래 코드는 switch문을 활용했지만 시간 초과가 떴다. 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(e=>e.replace("\r",""));
const a = input[0];
const que = [];
const answer = [];

for(let i = 0; i < a; i++){
    const arr = input[i+1].split(' ');
    
    switch(arr[0]){
        case 'push':
            que.push(Number(arr[1]));
            break;
        case 'pop':
            answer.push(que.length !== 0 ? que.shift() : -1);
            break;
        case 'size':
            answer.push(que.length);
            break;
        case 'empty':
            answer.push(que.length == 0 ? 1 : 0);
            break;
        case 'front':
            answer.push(que.length !== 0 ? que[0] : -1);
            break;
        case 'back':
            answer.push(que.length !== 0 ? que[que.length-1] : -1);
            break;
        default:
            break;
    }
}

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

 

위 코드에서는 'shift()' 메서드를 사용하여 큐의 맨 앞 요소를 제거하고 이로 인해 큐의 길이가 변하면서 모든 요소가 한 칸씩 앞으로 이동한다. 이 부분이 바로 시간 복잡도를 높일 수 있다.

 

 

 

M1 첫번째 풀이 방법)

 대신에 아래 코드와 같이 큐의 시작 부분과 끝 부분을 각각 가리키는 포인터를 사용하여 큐의 연산을 빠르게 수행할 수 있다. 이렇게 수정하면 pop() 연산에서 shift() 대신에 인덱스를 조절하여 큐의 맨 앞 요소를 추출하므로써, 시간 초과 문제를 개선할 수 있다. 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(e=>e.replace("\r",""));
const a = input[0];
const que = [];
let front = 0;
let back = 0;
const answer = [];

for(let i = 0; i < a; i++){
    const arr = input[i+1].split(' ');
    
    switch(arr[0]){
        case 'push':
            que[back++] = Number(arr[1]);
            break;
        case 'pop':
            answer.push(front !== back ? que[front++] : -1);
            break;
        case 'size':
            answer.push(back - front);
            break;
        case 'empty':
            answer.push(front == back ? 1 : 0);
            break;
        case 'front':
            answer.push(front !== back ? que[front] : -1);
            break;
        case 'back':
            answer.push(front !== back ? que[back - 1] : -1);
            break;
        default:
            break;
    }
}

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

 

 

M2 두번째 풀이 방법)

 클래스를 이용한 풀이이다. 각 명령별로 클래스에 메서드를 정의해서 이를 switch문에서 호출하는 식으로 구현했다. 

popLeft 메서드를 호출하는 부분에서 back-1을 하는 이유는 this.back이 큐의 다음에 추가될 위치를 가리키고 있기 때문이다. 따라서 가장 뒤쪽에 있는 원소는 this.back - 1의 위치에 있다.

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(e=>e.replace("\r",""));
const answer = [];

class Queue {
    constructor(){
        this.front = 0;
        this.back = 0;
        this.storage = [];
    }    

    push(x) {
        this.storage.push(x);
        this.back += 1;
    }

    popLeft(){
        if(this.front !== this.back) {
            const temp = this.storage[this.front];
            this.front+= 1;
            answer.push(temp);
        }else{
            answer.push(-1);
        }
    }

    size() {
        answer.push(this.back - this.front);
    }

    printFront() {
        answer.push(this.front !== this.back ? this.storage[this.front] : -1);
    }

    printBack() {
        answer.push(this.front !== this.back ? this.storage[this.back-1] : -1);
    }

    empty() {
        answer.push(this.front == this.back ? 1 : 0);
    }

    
}

const queue = new Queue();
const n = Number(input[0]);

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

    switch(s[0]){
        case 'push':
            queue.push(Number(s[1]));
            break;
        case 'pop':
            queue.popLeft();
            break;
        case 'size':
            queue.size();
            break;
        case 'empty':
            queue.empty();
            break;
        case 'front':
            queue.printFront();
            break;
        case 'back':
            queue.printBack();
            break;
        default:
            break;
    }
}

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