[바미] queuestack

문제

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

코드

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

const n = parseInt(input[0], 10);
const A = input[1].split(' ').map(Number);
const B = input[2].split(' ').map(Number);
const m = parseInt(input[3], 10);
const C = input[4].split(' ').map(Number);

const ret = [];

function solve(n, m, A, B, C) {
    let count = 0;
    for (let i = n - 1; i >= 0; i--) {
        if (!A[i] && m) {
            ret.push(B[i]);
            m--;
        }
    }
    let cIndex = 0;
    while (m--) {
        ret.push(C[cIndex]);
        cIndex++;
    }
}

solve(n, m, A, B, C);

console.log(ret.join(' '));

문제 해설

이번 문제는 역대급으로 시도가 많았던 문제였습니다.

 

스택은 들어온 값을 그대로 반환하는 반면, 큐는 먼저 들어온 값이 먼저 나가야 하는데 큐와 스택의 동작 방식을 제대로 고려하지 않은 접근으로 인해 시간 초과가 계속 발생했기 때문입니다.

 

문제는 각 자료구조가 큐 또는 스택으로 이루어진 N개의 자료구조를 다룹니다. 각 자료구조는 하나의 원소를 가지고 있으며, 우리는 주어진 입력(C 배열)을 처리하여 각 자료구조를 업데이트해야 합니다. 최종적으로 각 입력에 대해 어떤 값이 반환되는지를 출력해야 합니다.

 

문제의 핵심은 자료구조의 타입(큐 또는 스택)을 올바르게 처리하는 것입니다. 스택은 값을 그대로 반환하므로 단순히 값을 교체하면 되고, 큐는 값을 순서대로 처리해야 합니다.

 

시간 복잡도

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

 

초기화 단계에서 n 번 반복하여 큐 타입의 초기 값을 결과 배열에 추가하고, 그 후 m 번 반복하여 C 배열의 값을 결과 배열에 추가합니다. 

 

따라서 이 코드의 시간 복잡도는 O(N)이 됩니다.

공간 복잡도

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

 

입력으로 주어지는 A, B, C 배열은 각각 O(N)과 O(M) 공간을 차지하며, 결과를 저장하는 ret 배열은 최대 O(N + M) 공간을 차지할 수 있습니다.

 

따라서 이 코드의 공간 복잡도는 O(N + M)가 됩니다.