[Baekjoon] 18258번: 큐 2

 

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

18258번: 큐 2

 

---

 

문제 해결 과정

착안

큐(queue) 자료구조를 구현하는 문제이므로 STL에 구현되어있는 라이브러리를 이용하지 않고 문제에서 주어진 조건을 만족하는 형태의 큐 클래스 queue를 작성하되, 이때 큐 클래스가 가질 수 있는 최대 크기(capacity)가 주어지지 않았기 때문에 환형 큐의 형태로는 구현하기 어려울 것이라 판단하여 선형 큐 형태로 구현하였다.

 

구현

문제에서 push, pop을 제외한 명령어를 입력했을 때, 한 줄에 하나씩 결과를 출력하는 것을 요구하여 실제로는 size, empty, front, back 메서드는 일반적으로 값을 반환하도록 구현하지만 편의상 반환형 없이 출력을 수행하도록 구현하였다.

 

명령이 command line 입력으로 주어지기 때문에 STL의 string 클래스를 이용하여 입력된 명령어를 조건문으로 처리하여 각각 입력된 명령에 맞는 메서드를 호출하는 방식으로 문제를 해결할 수 있었다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <vector>

#pragma warning(disable : 4996)

using namespace std;

class queue
{
public:
	void push(int num)
	{
		Queue.push_back(num);
		Rear++;
		Count++;
	}

	void pop()
	{
		front();
		if (Count)
		{
			Front++;
			Count--;
		}
	}

	void size() { cout << Count << "\n"; }
	void empty() { cout << (Count ? 0 : 1) << "\n"; }

	void front()
	{
		if (!Count)
			cout << "-1\n";
		else
			cout << Queue.at(Front) << "\n";
	}

	void back()
	{
		if (!Count)
			cout << "-1\n";
		else
			cout << Queue.at(Rear) << "\n";
	}

private:
	vector<int> Queue;
	int Front = 0;
	int Rear = -1;
	size_t Count = 0;
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N;
	int num;
	string str;
	cin >> N;

	queue q;
	while (N--)
	{
		cin >> str;
		if (str == "push")
		{
			cin >> num;
			q.push(num);
		}
		else if (str == "front")	{ q.front(); }
		else if (str == "back")		{ q.back(); }
		else if (str == "size")		{ q.size(); }
		else if (str == "empty")	{ q.empty(); }
		else if (str == "pop")		{ q.pop(); }
	}

	return 0;
}

 

실행 결과

* 코드를 제출한 시점과 글 작성 시점이 달라, 주석 추가 등의 이유로 실행 결과의 코드 길이는 상이할 수 있음.

 

---

 

여태 접했던 문제들 중에서는 가장 실행 시간이 오래 소요되는 문제였는데, 특히 이번 문제의 경우는 입력과 출력의 빈도가 기존에 해결했던 문제들에 비하여 압도적으로 높아 C++ 표준 입출력 스트림에 대한 최적화 코드를 사용하였다(사용 방법 및 주의점 관련 글).

 

또한 큐 클래스에 대한 이해만 갖추고 있다면, 굳이 클래스 형태로 큐를 구현하지 않고 전역함수, 전역변수 등을 활용하여 문제를 해결하여도 전혀 지장은 없다.