[Beakjoon, C++] 18258번 : 큐2

백준 단계별 풀기에서 큐,덱 첫 번째 문제이다.

링크는 아래와 같다.

www.acmicpc.net/problem/18258

18258번: 큐 2

---

백준 18258번 문제, 입력, 출력

---

백준 18258번 입출력 예제 1

---

1. 큐의 구조는 위의 그림과 같다. 선입선출, 즉, 먼저 들어간 데이터가 먼저 나오는 방식으로, 스택의 선입후출과는 다른 개념이다. 스택에서는 아랫 부분이 막혀있었다면, 큐의 경우는 고속도로의 터널을 생각하면 될 듯하다. 흔히들, 사람들의 줄서기의 예시를 많이 든다. 먼저 와서 줄을 기다린 사람이 먼저 기다림을 해소할 수 있는 구조이다. 

 

2. C++ 에서는 queue 라이브러리를 제공한다. #include <queue>를 제일 윗 부분에서 선언해주면 사용할 수 있다. 

queue 라이브러리 출처 : http://www.cplusplus.com/reference/queue/queue/

Member functions에 있는 empty, size, front, back, push, emplace, pop, swap을 사용할 수 있다. 

 

3. 스택 첫 번째 문제와 마찬가지로, 첫번째로 int 타입 변수(numberOfCommand)에 몇 번의 명령을 할 것인지 입력 받는다.

 

4. numberOfCommand 변수만큼 for문을 돌면서, case 마다(if~else if~else) 명령어를 처리해 준다. 

 

5. 이번 것은 상당히 쉬웠지만, 시간초과의 문제를 직면하게 되었다. 찾아보니 9 10 라인의 코드를 추가해주고, endl 대신 \n으로 사용해 주어야 했다. 9라인은 cpp의 iostream을 c의 stdio와 동기화시켜주는 역할인데, false를 해줌으로써, 동기화를 하지 않게 한다. 동기화시 iostream 버퍼와 stdio 버퍼 두개를 모두 사용하는데, 이것을 끊어 줌으로써, iostream 버퍼만 사용하게 되고, 수행시간이 빨라지게 된다. 
 cin의 경우 scanf, getchar 보다 훨씬 더 무거워 수행시간이 오래 걸리기 때문에, 시간초과의 문제를 겪을 수 있다. 따라서, cin.tie(0)를 사용해서 cout으로 부터 cin을 untie 해준다. 이렇게 되면, cin을 받기전 버퍼를 flush해줘야 하는 점이 있지만, 속도는 빨라지게 된다.  

 또한, endl의 경우, 'cout<<endl' 보다 'cout<<"\n" '을 쓰는 것이 수행시간에서 10배 이상으로 단축시킬 수 있다고 한다.  

 

 

---

Visual Studio 2019 로 작성한 코드이다.

#include<iostream>
#include<queue>
#include<string>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int numberOfCommand;
    queue<int> que;
    string str_command;
 
    cin >> numberOfCommand;
 
    for (int i = 0; i < numberOfCommand; i++) {
        cin >> str_command;
 
        if (str_command == "push") {
            int number_queue;
            cin >> number_queue;
            que.push(number_queue);
        }
        else if (str_command == "pop") {
            if (!que.empty()) {
                cout << que.front() << "\n";
                que.pop();
            }
            else {
                cout << -1 << "\n";
            }    
        }
        else if (str_command == "size") {
            cout << que.size() << "\n";
        }
        else if (str_command == "empty") {
            if (que.empty()) {
                cout << 1 << "\n";
            }
            else {
                cout << 0 << "\n";
            }
        }
        else if (str_command == "front") {
            if (!que.empty()) {
                cout << que.front() << "\n";
            }
            else {
                cout << -1 << "\n";
            }
        }
        else if (str_command == "back") {
            if (!que.empty()) {
                cout << que.back() << "\n";
            }
            else {
                cout << -1 << "\n";
            }
        }
    }
 
    return 0;
}

이상으로 큐,덱 첫 번째 문제 큐2를 마치겠다.