[BaekJoon 10845][⚪4] 큐

❓ 문제

백준 10845 - “큐”

🎯 난이도

Silver ⚪4

🧠 풀이

1. 내 풀이 (queue)

- 알고리즘

• Data Structure, queue

- 설명

queue를 사용하는 풀이이다.

queue를 사용해서 로직을 하나하나 실행하는 방식이다. 어려울 것은 하나도 없는, 전형적인 queue 문제이다.

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

- 코드

내 풀이 코드

#include <iostream>

#include <queue>

#include <string>


using namespace std;

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

    int iN{};
    cin >> iN;

    queue<int> qInput{};

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

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

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

    return 0;
}

---

2. 추가 풀이 (deque)

- 알고리즘

• Data Structure

- 설명

deque을 사용하는 방식이다.

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

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

- 코드

내 풀이 코드

#include <iostream>

#include <deque>

#include <string>


using namespace std;

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

    int iN{};
    cin >> iN;

    deque<int> dqInput{};

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

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

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

    return 0;
}

---

💭 후기

이전의 스택문제와 완전히 동일하고, 사용하는 컨테이너만 다른 문제이다. queue를 사용하는 것이 본래 문제의 의도이지만, deque으로 치환해서 풀어도 전혀 문제는 없다. 하지만 문제의 이름부터가 queue이므로 웬만하면 queue를 사용하는 편이 좋을 것 같긴 하다.