[C++ 알고리즘] 백준 18258번 : 큐 2

 


BruteForce

큐 2

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

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

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이과정

는 배열을 사용하는 순차 자료구조나 포인터를 사용하는 연결 자료구조 방식을 이용해 구현할 수 있다.
배열 을 통해 큐를 구현할 경우 배열 크기를 미리 할당해놓기 때문에 큐의 크기 변경이 어려우므로 메모리 사용의 효율성이 떨어진다.
연결 리스트 를 통해 큐를 구현할 경우 큐의 크기 변경이 자유롭다는 장점이 있으므로 이 포스트에서는 큐를 연결 리스트 를 통해 구현하였다.

클래스 설명
QueueElement 스택의 자료를 가지며 다음 원소의 주소를 가진다.
MyQueue push, pop 등 FIFO 구조가 적용된 스택이다.
Console 사용자의 입·출력을 담당한다.


구현하는 과정에서 BOJ 채점 시 시간초과를 발생시켰던 두 가지 이슈가 있었다.

1. 큐의 사이즈 반환 시

초기에는 getSize() 함수 내에서 함수를 호출할 때마다 연결리스트의 모든 원소를 검색하여 크기를 재는 로직을 사용하였다. 하지만 MyQueue 클래스 내에서 큐의 크기를 가지는 멤버 변수 size를 만들어 push, pop 할 때마다 size의 크기를 다루니 속도가 향상될 수 있었다.

2. 입출력 시

1 의 문제를 해결하고 나서도 시간초과가 되어 검색해보니, C++의 cin, coutendl은 출력 버퍼를 flush하는 느린 연산이라고 한다. 따라서 cout<<endl; 대신 cout<<'\n' 을 사용하고 main 함수에 cin.tie(NULL); ios::sync_with_stdio(false); 를 사용하니 출력 속도가 상승하여 시간 초과 없이 잘 작동하였다.

코드

#include <iostream>
#include <stack>

using namespace std;

class QueueElement {
private:
    int data;
    QueueElement* next;
public:
    QueueElement() { data = -1; next = NULL; }
    void setData(int data) { this->data = data; }
    void setNext(QueueElement*next) { this->next = next; }
    int getData() { return data; }
    QueueElement* getNext() { return next; }
};

class MyQueue {
private:
    QueueElement* front;
    QueueElement* back;
    int size;
public:
    MyQueue() { front = back = NULL; size = 0; }
    void push(int x);
    int pop();
    int getSize();
    bool isEmpty();
    int getFront() {
        if (front != NULL) return front->getData();
        else return -1;
    }
    int getBack() {
        if (back != NULL) return back->getData();
        else return -1;
    }
};
void MyQueue::push(int x) {
    //공백 큐인 경우
    if (isEmpty()) {
        QueueElement* temp = new QueueElement();
        temp->setData(x);
        temp->setNext(NULL);
        front = temp;
        back = temp;
    }
    //공백 큐가 아닌 경우 back에 삽입
    else {
        QueueElement* temp = new QueueElement();
        temp->setData(x);
        temp->setNext(back->getNext());
        back->setNext(temp);
        back = temp;
    }
    size++;
}
int MyQueue::pop() {
    int ret;
    if (!isEmpty()) {
        QueueElement* temp = front;
        ret = temp->getData();
        front = temp->getNext();
        if (front == NULL) back = NULL;
        delete temp;
        size--;
    }
    else {
        ret = -1;
    }

    return ret;
}
int MyQueue::getSize() {
    return size;
}
bool MyQueue::isEmpty() {
    if (front == NULL) return true;
    return false;
}

class Console {
    string cmd;
    int n;
    int input;
    MyQueue queue;
public:
    void run();
};
void Console::run() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> cmd;
        if (cmd.compare("push") == 0) {
            cin >> input;
            queue.push(input);
        }
        else if (cmd.compare("pop") == 0) {
            cout << queue.pop() << '\n';
        }
        else if (cmd.compare("size") == 0) {
            cout << queue.getSize() << '\n';
        }
        else if (cmd.compare("empty") == 0) {
            queue.isEmpty() ? cout << 1 : cout << 0;
            cout << '\n';
        }
        else if (cmd.compare("front") == 0) {
            cout << queue.getFront() << '\n';
        }
        else if (cmd.compare("back") == 0) {
            cout << queue.getBack() << '\n';
        }
        else { }
    }
}

int main() {
    //출력 속도 상승
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    Console console;
    console.run();
    return 0;
}

결과

image


:bookmark: REFERENCE
[c++] 18258 큐 시간초과 질문입니다