[BOJ] 백준 18258번: 큐 2 (C++)

 

- 문제 출처 : https://www.acmicpc.net/problem/18258

---

1. 생각

그동안 스택 관련 문제를 4개 정도 풀어봤고, 이번에는 새로운 자료구조인 '큐'에 대해서 풀어보기로 했다.

스택은 LIFO (또는 FILO) 방식으로, 마지막으로 온 자료가 가장 먼저 나가는 구조이다.

그와 반대로, 큐는 FIFO (또는 LILO) 방식으로, 먼저 온 자료가 가장 먼저 나가는 구조이다.

 

이전 C++에서 사용했던 것처럼 큐도 STL 에 있는 자료구조를 들고와서 사용할 것이고,

사용법은 스택과 굉장히 유사했다.

 

문제는 기본적인 큐의 사용을 알아보기 위한 길라잡이 문제이며,

명령어 그대로 해당 동작을 사용하면 되는 것으로 파악했다.

 

2. 난관 & 해결 방법

#include <iostream>
#include <string>
#include <queue>

 

stack을 불러와서 썼던 것처럼 queue도 include 해준다.

 

int n, num;
std::string s;
std::queue <int> q;
std::cin.tie(NULL);
std::ios::sync_with_stdio(false);
std::cin >> n;

 

초기화 단계인데, 이번 과제는 명령어 개수가 200만개까지 받을 수 있게 설정해뒀기에

시간제한에 걸리지 않도록 tie(NULL) 와 ios::sync_with_stdio(false) 를 이용해 딜레이를 없앴다.

(cin.tie(NULL)은 cout으로부터 cin을 untie 해주어 빨라진다고 한다.)

 

그리고 std::queue <int> q; 로 queue를 만들어주었다.

 

for (int i = 0; i < n; i ++){
    std::cin >> s;
    if (s == "push"){
        std::cin >> num;
        q.push(num);
    }
    else if (s == "pop"){
        if (q.empty())
            std::cout << -1 << "\n";
        else {
            std::cout << q.front() << "\n";
            q.pop();
        }
    }
    else if (s == "size"){
        std::cout << q.size() << "\n";
    }
    else if (s == "empty"){
        std::cout << q.empty() << "\n";
    }
    else if (s == "front"){
        if (q.empty())
            std::cout << -1 << "\n";
        else
            std::cout << q.front() << "\n";
    }
    else if (s == "back"){
        if (q.empty())
            std::cout << -1 << "\n";
        else
            std::cout << q.back() << "\n";
    }
}

 

for문에서는 cin을 통해 읽어가며 명령어들을 분류했는데,

이전 코드에서 getline을 통해 한 줄씩 읽는 방식을 사용하려다,

push의 case에서는 숫자까지 String형태로 받게 되므로

차라리 해당 case에서만 cin을 두번 쓰게 만드는 방식을 사용했다.

 

그리고 여기서 또 알게 된 사실,

std::endl 을 통해서 개행을 출력하는 것보다, "\n" 으로 출력하는 것이 훨씬 속도가 빠르다고 한다.

endl은 출력버퍼를 비우고, \n은 비우지 않아 속도의 차이가 많이 난다고 한다.

 

3. 코드 및 결론

[ 전체 코드 ]

#include <iostream>
#include <string>
#include <queue>

int main(void){
    int n, num;
    std::string s;
    std::queue <int> q;
    std::cin.tie(NULL);
    std::ios::sync_with_stdio(false);
    std::cin >> n;

    for (int i = 0; i < n; i ++){
        std::cin >> s;
        if (s == "push"){
            std::cin >> num;
            q.push(num);
        }
        else if (s == "pop"){
            if (q.empty())
                std::cout << -1 << "\n";
            else {
                std::cout << q.front() << "\n";
                q.pop();
            }
        }
        else if (s == "size"){
            std::cout << q.size() << "\n";
        }
        else if (s == "empty"){
            std::cout << q.empty() << "\n";
        }
        else if (s == "front"){
            if (q.empty())
                std::cout << -1 << "\n";
            else
                std::cout << q.front() << "\n";
        }
        else if (s == "back"){
            if (q.empty())
                std::cout << -1 << "\n";
            else
                std::cout << q.back() << "\n";
        }
    }
}

 

[ 결론 ]

 

큐라는 자료구조 자체가 크게 어렵게 생각할만한 구조는 아니어서 문제 자체는 쉬웠으나,

시간 제한에 의해서 여러번 retry 해본 처음 과제였다.

그동안 시간 제한이 문제된 적이 없어서 당황스러웠지만 해결법이 정말 많이 존재했고,

저 방법들로도 풀지 못하면 아예 배열이나 리스트를 이용해서 큐를 만들면 더 빨라지지 않을까 싶다.

 

이제 아주 조금 백준 문제들에 익숙해지고 있긴 하지만, 아직은 많이 부족하다.

더 다양한 자료구조에 대한 문제들을 풀어보고, 알고리즘 문제들로 제대로 넘어가보자.