백준 10828번 스택

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

---

풀이/접근 방법(JavaScript)

시간초과 문제

자바스크립트의 경우 계속 시간초과가 나와서 통과하지 못했다.
결국 구글링을 해보았는데, C++에서 풀었던 것처럼 명령을 수행할때마다 출력을 시켜줘서 시간초과가 나는 것이었다.
(for문 마다 console.log를 수행하는 것은 속도가 매우 느리다!)
그래서 정답 값들을 answer 배열에 넣어주고, 마지막에 join함수로 한꺼번에 출력해주었더니 통과할 수 있었다.

처음엔 if문으로 문제 그대로 코드를 작성했으나, switch 문을 사용해 작성했더니 코드가 훨씬 간결하고 깔끔해졌다.

코드(JavaScript)

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

const stack = [];
const answer = [];
const len = Number(input[0]);

for(let i=1; i<=len; i++){
    let cmd = input[i].split(' ');
    switch(cmd[0]) {
        case 'push':
            stack.push(cmd[1]);
            break;
        case 'pop':
            answer.push(stack.pop() || -1);
            break;
        case 'size':
            answer.push(stack.length);
            break;
        case 'empty':
            answer.push(stack[0] ? 0 : 1);
            break;
        case 'top':
            answer.push(stack[stack.length-1] || -1);
            break;
    }
}

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

---

풀이/접근 방법(C++) ver1.

c++의 stack STL을 사용해 풀었다.
#include <stack> 헤더파일 작성해준 뒤 stack<int> stack; 으로 스택을 선언한다.

코드(C++)

#include <iostream>
#include <stack>
using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    
    stack<int> stack;
    for(int i=0; i<n; i++){
        string cmd;
        cin >> cmd;
        if(cmd == "push"){
            int num;
            cin >> num;
            stack.push(num);
        }
        else if(cmd == "pop"){
            if(!stack.empty()){
                cout << stack.top() << '\n';
                stack.pop();
            }
            else cout << -1 << '\n';
        }
        else if(cmd == "size"){
            cout << stack.size() << '\n';
        }
        else if(cmd == "empty"){
            cout << stack.empty() << '\n';
        }
        else if(cmd == "top"){
            if(!stack.empty()) cout << stack.top() << '\n';
            else cout << -1 << '\n';
        }
        
    }
    return 0;
}

풀이/접근 방법(C++) ver2.

배열로 스택을 직접 구현해 풀었다.

코드(C++)

#include <iostream>

using namespace std;

int stack[10000], topIdx = -1;

void push(int n) {
    stack[++topIdx] = n;
}

int empty() {
    if(topIdx < 0) return 1;
    else return 0;
}

int pop(){
    if(!empty()){
        return stack[topIdx--];
    }
    else return -1;
}

int size(){
    if(!empty()) return topIdx+1;
    else return 0;
}

int top(){
    if(!empty()){
        return stack[topIdx];
    }
    else return -1;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    
    for(int i=0; i<n; i++){
        string cmd;
        cin >> cmd;
        if(cmd == "push"){
            int num;
            cin >> num;
            push(num);
        }
        else if(cmd == "pop") cout << pop() << '\n';
        else if(cmd == "size") cout << size() << '\n';
        else if(cmd == "empty") cout << empty() << '\n';
        else if(cmd == "top") cout << top() << '\n';      
    }
    return 0;
}