[바미] 스택 2

문제

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

코드

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);
const stack = [];
const output = [];

for (let i = 0; i < N; i++) {
    const command = commands[i].split(' ');

    switch (command[0]) {
        case '1':
            // 정수 X를 스택에 넣는다.
            stack.push(parseInt(command[1], 10));
            break;
        case '2':
            // 스택에서 정수를 빼고 출력한다. 없으면 -1 출력.
            output.push(stack.length > 0 ? stack.pop() : -1);
            break;
        case '3':
            // 스택에 들어있는 정수의 개수를 출력한다.
            output.push(stack.length);
            break;
        case '4':
            // 스택이 비어있으면 1, 아니면 0을 출력한다.
            output.push(stack.length === 0 ? 1 : 0);
            break;
        case '5':
            // 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없으면 -1.
            output.push(stack.length > 0 ? stack[stack.length - 1] : -1);
            break;
    }
}

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

코드 설명

for (let i = 0; i < N; i++) {
    const command = commands[i].split(' ');

    switch (command[0]) {
        case '1':
            // 정수 X를 스택에 넣는다.
            stack.push(parseInt(command[1], 10));
            break;
        case '2':
            // 스택에서 정수를 빼고 출력한다. 없으면 -1 출력.
            output.push(stack.length > 0 ? stack.pop() : -1);
            break;
        case '3':
            // 스택에 들어있는 정수의 개수를 출력한다.
            output.push(stack.length);
            break;
        case '4':
            // 스택이 비어있으면 1, 아니면 0을 출력한다.
            output.push(stack.length === 0 ? 1 : 0);
            break;
        case '5':
            // 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없으면 -1.
            output.push(stack.length > 0 ? stack[stack.length - 1] : -1);
            break;
    }
}

명령을 처리하는 프로그램을 담당하는 부분입니다. 저는 개인적으로 여러 조건에 따라 처리해야 할 부분이 정확하다면 switch문을 사용하는 편입니다.

 

물론 if() else if()를 반복하여 풀 수 있지만 코드 자체가 명확해지고, 읽고 이해하기 쉬워지기도 하고, 명령 코드를 case 레이블로 사용하여 오타나 잘못된 명령 코드로 인한 오류의 가능성도 현저히 줄어들도록 만들 수 있을 뿐만 아니라 case가 명시적으로 구분되어 있기 때문에 잘못된 코드 입력시엔 switch문에 의해 처리되지 않는 부분도 있어 이런 경우엔 switch문을 애용하는 편입니다.

문제 해설

이 문제는 제목에서 알 수 있듯이 스택을 이용하여 여러 명령을 처리하는 문제입니다.

스택은 선입후출(Last In, First Out / LIFO) 원리를 따르는 자료구조라는 것은 다들 아실거라 생각합니다.

여기서는 여러 기본적인 스택 연산을 수행하는 명령을 처리하는 알고리즘을 구현해야 합니다.

 

처리해야 하는 명령들은 다음과 같습니다.

• 정수 X를 스택에 넣는다. (1 X)
• 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. (2)
• 스택에 들어있는 정수의 개수를 출력한다. (3)
• 스택이 비어있으면 1, 아니면 0을 출력한다. (4)
• 스택의 가장 위에 있는 정수를 출력한다. (5)

JS의 배열의 push와 pop 메소드를 사용하여 쉽게 풀어낼 수 있는 문제입니다.

 

시간 복잡도

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

 

각 명령을 처리하는 데 일반적으로 상수 시간 O(1)이 걸립니다. 

이 말은 명령 하나를 처리하는 데 시간이 명령의 수와 비례하지 않고 일정하다는 의미입니다.

 

예를 들어, 스택에 원소를 추가하거나 제거하는 push와 pop 연산은 일반적으로 O(1)의 시간 복잡도를 가지게 되는데 N개의 명령을 모두 처리하는 데는 N번의 O(1) 연산이 수행되므로 총 시간 복잡도는 O(N)이 됩니다.

 

여기서 N은 처리해야 할 명령들의 총 개수입니다.

공간 복잡도

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

 

모든 명령이 스택에 원소를 추가하는 명령(1 X)이 최악의 경우겠네요.

이 경우 스택은 최대 N개의 원소를 저장할 수 있게 되기 때문에 스택의 공간 복잡도는 최대 원소 수인 N에 비례하여 O(N)이 됩니다.

 

여기서 N은 스택에 저장될 수 있는 최대 원소의 수를 의미합니다.