[백준] 18258 - 큐 2

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

 

 

 

 

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

// const queue = [];
// const n = input[0];

// for (let i = 1; i<n; i++){
//     const [cmd, value] = input[i].split(" ");

//     switch(cmd){
//         case "push":
//             queue.push(value);
//             break;
//         case "pop":
//             console.log(queue.shift() || -1);
//             break;
//         case "size":
//             console.log(queue.length);
//             break;
//         case "empty":
//             console.log(queue.length === 0 ? 1 : 0);
//             break;
//         case "front":
//             console.log(queue[0] || -1);
//             break;
//         case "back":
//             console.log(queue[queue.length - 1] || -1);
//             break;

//     }
// }

-> 시간 초과!!

 

 

Code

개선된 코드 (시간 초과 방지)

1. 출력값을 배열에 모아서 마지막에 한 번에 출력
2. shift 대신 인덱스를 사용해 O(1)로 pop 구현

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const n = +input[0];
const queue = [];
let head = 0; // 큐의 앞을 가리키는 인덱스
const results = [];

for (let i = 1; i <= n; i++) {
    const [cmd, value] = input[i].split(" ");

    switch(cmd){
        case "push":
            queue.push(Number(value));
            break;
        case "pop":
            results.push(head < queue.length ? queue[head++] : -1);
            break;
        case "size":
            results.push(queue.length - head);
            break;
        case "empty":
            results.push(head === queue.length ? 1 : 0);
            break;
        case "front":
            results.push(head < queue.length ? queue[head] : -1);
            break;
        case "back":
            results.push(head < queue.length ? queue[queue.length - 1] : -1);
            break;
    }
}

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

 

 shift의 문제점

• queue.shift()는 배열의 맨 앞요소를 제거합니다

• 하지만 자바스크립트 배열은 맨 앞 요소를 제거하면

나머지 모든 요소를 한 칸씩 앞으로 이동시킵니다.

• 즉, 시간 복잡도 O(N) (N은 배열 길이)

→ 명령이 많아질수록 느려짐

---

2. 인덱스를 사용한 O(1) pop

• 배열의 맨 앞을 실제로 제거하지 않고,

앞을 가리키는 인덱스(head)만 증가시킵니다.

 

 

 

Code 설명

const n = +input[0];

• 입력의 첫 줄(명령 개수)을 숫자로 변환해서 n에 저장합니다.
• +는 Number()를 짧고 간단하게 쓴 것

const queue = [];
let head = 0; // 큐의 앞을 가리키는 인덱스
const results = [];

• queue: 큐 역할을 할 배열입니다.
• head: 큐의 맨 앞(가장 먼저 들어온 값)을 가리키는 인덱스입니다. (shift 대신 사용)
• results: 각 명령의 결과를 저장할 배열입니다. (마지막에 한 번에 출력)

---

for (let i = 1; i <= n; i++) {
    const [cmd, value] = input[i].split(" ");

• 두 번째 줄부터 n번째 줄까지 각 명령어를 처리합니다.
• cmd는 명령어, value는 명령어에 따라 필요한 값(예: push X의 X)

---

명령어별 처리

1. push X

case "push":
    queue.push(Number(value));
    break;

• 큐의 맨 뒤에 값을 추가합니다.

2. pop

case "pop":
    results.push(head < queue.length ? queue[head++] : -1);
    break;

• 큐가 비어있지 않으면 맨 앞 값을 결과에 추가하고, head를 1 증가시킵니다.
• 큐가 비어있으면 -1을 결과에 추가합니다.

3. size

case "size":
    results.push(queue.length - head);
    break;

• 큐에 남아있는(아직 pop되지 않은) 원소의 개수를 결과에 추가합니다.

4. empty

case "empty":
    results.push(head === queue.length ? 1 : 0);
    break;

• 큐가 비어있으면(남은 원소가 없으면) 1, 아니면 0을 결과에 추가합니다.

5. front

case "front":
    results.push(head < queue.length ? queue[head] : -1);
    break;

• 큐가 비어있지 않으면 맨 앞 값을 결과에 추가, 비어있으면 -1을 추가합니다.

6. back

case "back":
    results.push(head < queue.length ? queue[queue.length - 1] : -1);
    break;

• 큐가 비어있지 않으면 맨 뒤 값을 결과에 추가, 비어있으면 -1을 추가합니다.

---

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

• 모든 결과를 줄바꿈(\\\\n)으로 합쳐서 한 번에 출력합니다. (시간 초과 방지, 빠른 출력)