[백준] 10845 큐, 18258 큐2

문제 설명

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

10845번: 큐

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

18258번: 큐 2

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램 만들기

 

• push X : 정수 X를 큐에 넣기
• pop : 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력. 만약 큐에 들어있는 정수가 없는 경우에는 -1 출력
• size : 큐에 들어있는 정수의 개수를 출력
• empty : 큐가 비어있으면 1, 아니면 0을 출력
• front : 큐의 가장 앞에 있는 정수를 출력. 만약 큐에 들어있는 정수가 없는 경우에는 -1 출력
• back : 큐의 가장 뒤에 있는 정수를 출력. 만약 큐에 들어있는 정수가 없는 경우에는 -1 출력

 

두 문제다 구현은 같지만 18258_큐2가 좀 더 입력이 많아서 시간초과가 나기 쉽다

(10845_큐는 조금 덜 하다. 밑에 코드를 보면 모르고 scanf대신 cin을 쓴 부분이 하나 있는데, 그래도 통과되었다)

 

문제 풀이법

[백준 10828 스택]과 같은 문제이다 (stack이냐, queue냐의 차이)

queue를 선언하여 주어지는 명령어에 맞게 그대로 구현하면 된다

주의해야 할 점은 명령어 설명에도 있지만 pop, front, back에서 스택이 비어있는지 먼저 확인 후 실행

 

cin과 cout을 쓰면 시간 초과가 난다는 점 주의!

cin과 cout을 사용하려면 다음과 같이 입력한 후 사용한다

ios::sync_with_stdio(0);
    cin.tie(0);

 

소스 코드

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    
    queue<int> q;
    for (int i = 0; i < n; i++)
    {
        string str;
        cin >> str;
        
        if (str == "push")
        {
            int tmp;
            scanf("%d", &tmp);
            q.push(tmp);
        }
        
        else if (str == "pop")
        {
            if (!q.empty())
            {
                printf("%d\n", q.front());
                q.pop();
            }
            else
                printf("-1\n");
        }
        else if (str == "size")
            printf("%d\n", q.size());
        else if (str == "empty")
            printf("%d\n", q.empty());
        else if (str == "front")
        {
            if (!q.empty())
                printf("%d\n", q.front());
            else
                printf("-1\n");
        }
        else if (str == "back")
        {
            if (!q.empty())
                printf("%d\n", q.back());
            else
                printf("-1\n");
        }
    }
    return 0;
}

 

cin과 cout을 사용한 경우

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    queue<int> q;
    for (int i = 0; i < n; i++)
    {
        string str;
        cin >> str;
        
        if (str == "push")
        {
            int tmp;
            cin >> tmp;
            q.push(tmp);
        }
        
        else if (str == "pop")
        {
            if (!q.empty())
            {
                cout << q.front() << "\n";
                q.pop();
            }
            else
                cout << "-1\n";
        }
        else if (str == "size")
            cout << q.size() << "\n";
        else if (str == "empty")
            cout << q.empty() << "\n";
        else if (str == "front")
        {
            if (!q.empty())
                cout << q.front() << "\n";
            else
                cout << "-1\n";
        }
        else if (str == "back")
        {
            if (!q.empty())
                cout << q.back() << "\n";
            else
                cout << "-1\n";
        }
    }
    return 0;
}