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, cout과 endl은 출력 버퍼를 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;
}
결과
REFERENCE
[c++] 18258 큐 시간초과 질문입니다