[BaekJoon 10828][⚪4] 스택

❓ 문제

백준 10828 - “스택”

🎯 난이도

Silver ⚪4

🧠 풀이

1. 내 풀이 (동적 배열)

- 알고리즘

• Data Structure

- 설명

vector를 사용하는 풀이이다.

문제의 본래 의도는 stack이지만, 대신 vector를 사용하는 풀이이다. stack의 모든 기능은 vector로 가능하므로, 완전 치환 가능하다.

모든 로직은 O(1)이고, N번 반복하므로 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>

#include <string>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{};
    cin >> iN;

    vector<int> vecInput{};
    vecInput.reserve(iN);

    while(iN--)
    {
        string strInput{};
        cin >> strInput;

        // push 실행
        if(strInput == "push")
        {
            int iInput{};
            cin >> iInput;

            vecInput.push_back(iInput);
        }
        // pop 실행
        else if(strInput == "pop")
        {
            if(!vecInput.empty())
            {
                cout << vecInput.back() << '\n';
                vecInput.pop_back();
            }
            else
            {
                cout << -1 << '\n';
            }
        }
        // size 실행
        else if(strInput == "size")
        {
            cout << vecInput.size() << '\n';
        }
        // empty 실행
        else if(strInput == "empty")
        {
            cout << (vecInput.empty() ? 1 : 0) << '\n';
        }
        // top 실행
        else if(strInput == "top")
        {
            cout << (vecInput.empty() ? -1 : vecInput.back()) << '\n';
        }
    }

    return 0;
}

---

2. 추가 풀이 (stack)

- 알고리즘

• Data Structure, stack

- 설명

stack을 사용하는 방식이다.

문제의 본래 의도대로 stack을 사용하는 풀이이다. 로직은 위의 풀이와 완전히 같고, 컨테이너만 stack으로 치환했다.

위와 똑같이 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <stack>

#include <string>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{};
    cin >> iN;

    stack<int> stInput{};

    while(iN--)
    {
        string strInput{};
        cin >> strInput;

        // push 실행
        if(strInput == "push")
        {
            int iInput{};
            cin >> iInput;

            stInput.push(iInput);
        }
        // pop 실행
        else if(strInput == "pop")
        {
            if(!stInput.empty())
            {
                cout << stInput.top() << '\n';
                stInput.pop();
            }
            else
            {
                cout << -1 << '\n';
            }
        }
        // size 실행
        else if(strInput == "size")
        {
            cout << stInput.size() << '\n';
        }
        // empty 실행
        else if(strInput == "empty")
        {
            cout << (stInput.empty() ? 1 : 0) << '\n';
        }
        // top 실행
        else if(strInput == "top")
        {
            cout << (stInput.empty() ? -1 : stInput.top()) << '\n';
        }
    }

    return 0;
}

---

💭 후기

stack 문제는 모두 vector로 치환 가능하다. 게다가 vector를 사용하면 'reserve'로 재할당 방지, 연속 메모리 구조로 인한 높은 '캐시 친화성'이라는 장점까지 있으므로 대부분의 경우에는 vector를 사용하는 편이 좋다.