백준 10828번: 스택

solved.ac 기준 실버 4

10828번: 스택

스택(Stack)

스택(Stack)은 후입선출(Last-in first-out, LIFO) 방식으로 자료를 삽입하거나 제거할 수 있는 자료구조 중 하나이다.

이번 문제는 이 스택을 구현하고 이를 명령어로 실행하는 것을 요구한다.

출처: 위키백과

 

구현해야 하는 명령 다섯가지

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

아이디어/참고

스택의 추상 자료형(ADT)은 다음과 같다. (출처: Data Structures & Algorithms in C++, 2nd Edition)

Algorithm size():
	return t+1
Algorithm empty():
	return (t<0)
Algorithm top():
	if empty() then
		throw StackEmpty exception
	return S[t]
Algorithm push(e):
	if size() = N then
		throw StackFull exception
	t←t+1
	S[t]←e
Algorithm pop():
	if empty() then
		throw StackEmpty exception
	t←t−1

이를 클래스로 만들면 될 것 같다. 그리고 해당 문제는 정수만 구현하면 된다.

 

명령어 입력

이 문제는 단순 스택의 함수를 호출하는 것이 아닌 명령어가 입력으로 주어지면 호출하는 방식이므로, 명령어를 받아들이고 조건문을 통하여 명령어가 맞으면 해당 명령을 실행하는 식으로 코드를 짜면 될 것 같다.

int n 선언
string command 선언
Stack s 선언
n 입력받음

for i=0, i<n, i++
	cmd 입력받음
    if cmd = size then
    	s.size() 출력
    else if cmd = empty then
    	s.empty() 출력
    else if cmd = top then
    	s.top() 출력
    else if cmd = push then
    	int x 선언하고 입력받기
        s.push() 실행
    else if cmd = pop then
    	s.pop() 출력

테스트 환경

- OS: Windows 10

- IDE: Visual Studio Code

- 컴파일러: GCC

 

첫 번째 답안

- 코드 용량: 1988KB

- 실행 시간: 312ms

- https://www.acmicpc.net/source/20033960

#include <iostream>
#include <string>

using namespace std;

#define CAPACITY 1000

class CustomStack {
    private:
        int* stack_array;
        int capacity;
        int t;
    public:
        CustomStack(int cap){
            stack_array = new int[cap];
            capacity = cap;
            t = -1;
        }
        int size() const{
            return (t+1);
        }
        int empty() const{
            if (t<0)
                return 1;
            else
                return 0;
        }
        int top() const{
            if (empty() == 1) return -1;
            return stack_array[t];
        }
        void push(int x){
            t++;
            stack_array[t] = x;
        }
        int pop(){
            if (empty() == 1) return -1;
            int temp = stack_array[t];
            t--;
            return temp;
        }
};

int main()
{
    int n;
    string cmd;
    CustomStack s(CAPACITY);

    cin >> n;
    for (int i=0; i<n; i++){
        cin >> cmd;
        if (cmd == "size"){
            cout << s.size() << '\n';
        }
        else if (cmd == "empty"){
            cout << s.empty() << '\n';
        }
        else if (cmd == "top"){
            cout << s.top() << '\n';
        }
        else if (cmd == "push"){
            int x;
            cin >> x;
            s.push(x);
        }
        else if (cmd == "pop"){
            cout << s.pop() << '\n';
        }
    }

    return 0;
}

두 번째 답안

- 문제를 풀다보니 실행시간이 312ms나 나올 게 있나..? 하는 생각이 들어서 찾아봤더니, std::cin과 std::cout이 printf와 scanf보다 속도가 엄청 느리다는 이야기가 있었다. 다른 사람들이 C++로 작성한 것을 참고해보니 전부 printf와 scanf를 사용하였다.

- 참고: https://algospot.com/forum/read/2496/

std::cin은 sync_with_stdio를 사용하지 않으면 scanf와 비교하여 수행시간이 큰 차이가 난다.

 

- 코드 용량: 1172KB

- 실행 시간: 4ms

- https://www.acmicpc.net/source/20034694

#include <stdio.h>
#include <string.h>

#define CAPACITY 1000

class CustomStack {
    private:
        int* stack_array;
        int capacity;
        int t;
    public:
        CustomStack(int cap){
            stack_array = new int[cap];
            capacity = cap;
            t = -1;
        }
        int size() const{
            return (t+1);
        }
        int empty() const{
            if (t<0)
                return 1;
            else
                return 0;
        }
        int top() const{
            if (empty() == 1) return -1;
            return stack_array[t];
        }
        void push(int x){
            t++;
            stack_array[t] = x;
        }
        int pop(){
            if (empty() == 1) return -1;
            int temp = stack_array[t];
            t--;
            return temp;
        }
};

int main()
{
    int n;
    char cmd[10];
    CustomStack s(CAPACITY);

    scanf("%d", &n);
    for (int i=0; i<n; i++){
        scanf("%s", cmd);
        if (strcmp(cmd,"size") == 0){
            printf("%d\n", s.size());
        }
        else if (strcmp(cmd,"empty") == 0){
            printf("%d\n", s.empty());
        }
        else if (strcmp(cmd,"top") == 0){
            printf("%d\n", s.top());
        }
        else if (strcmp(cmd,"push") == 0){
            int x;
            scanf("%d", &x);
            s.push(x);
        }
        else if (strcmp(cmd,"pop") == 0){
            printf("%d\n", s.pop());
        }
    }
    return 0;
}

std::cin과 std::cout을 printf와 scanf로 바꾸었더니 312ms -> 4ms로 확연히 차이가 난다.