18258번 큐2

문제링크 : www.acmicpc.net/problem/18258

18258번: 큐 2

 

---

---

버전 1. vector를 이용해 Q class를 만들어서 진행(시간 초과)

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Q {
public:
	vector<int> v;
	void push(int x) { v.push_back(x); }
	void pop() {
		if (v.size() == 0) { cout << "-1\n"; }
		else {
			cout << v.front() << "\n";
			vector<int>::iterator iter = v.begin();
			v.erase(iter);
		}
	}
	void size() {cout << v.size() << "\n";}
	void empty() {
		if (v.size() == 0) { cout << "1\n"; }
		else { cout << "0\n"; }
	}
	void front() { 
		if (v.size() == 0) { cout << "-1\n"; }
		else { cout << v[0] << "\n"; }
	}
	void back(){
		if (v.size() == 0) { cout << "-1\n"; }
		else { cout << v[v.size()-1] << "\n"; }
	}
};

int main() {
	int N = 0;
	cin >> N;
	Q q;
	while (N--) {
   	 	cin.tie(0);
		cin.sync_with_stdio(0);
		string commend = "";
		cin >> commend;
		if (commend == "push") {
			int a = 0;
			cin >> a;
			q.push(a);
		}
		else if (commend == "pop") { q.pop(); }
		else if (commend == "size") { q.size(); }
		else if (commend == "empty") { q.empty(); }
		else if (commend == "front") { q.front(); }
		else if (commend == "back") { q.back(); }
	}
	return 0;
}

 

 

버전 2. main에서 vector로 queue 구현(시간 초과)

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
	int N = 0;
	cin >> N;

	vector<int>v;
	while (N--) {
    	cin.tie(0);
		cin.sync_with_stdio(0);
		string commend = "";
		cin >> commend;
		if (commend == "push") {
			int a = 0;
			cin >> a;
			v.push_back(a);
		}
		else if (commend == "pop") {
			if (v.size() == 0) { cout << "-1\n"; }
			else {
				cout << v[0] << "\n";
				v.erase(v.begin());
			}
		}
		else if (commend == "size") { cout << v.size() << "\n"; }
		else if (commend == "empty") {cout << v.empty() << "\n";}
		else if(commend == "front"){
			if (v.size() == 0) { cout << "-1\n"; }
			else { cout << v.front() << "\n"; }
		}
		else if (commend == "back") {
			if (v.size() == 0) { cout << "-1\n"; }
			else { cout << v.back() << "\n"; }
		}
	}
	return 0;
}

 

 

 

버전 3. STL <queue>사용 (메모리 : 8412KB   시간 : 384ms)

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N = 0;
	cin >> N;
	queue<int> q;
	int a = 0;
	while (N--) {
		string commend = "";
		cin >> commend;
		if (commend == "push") {
			cin >> a;
			q.push(a);
		}
		else if (commend == "pop") {
			if (q.empty()) { cout << "-1\n"; }
			else{
				cout << q.front() << "\n";
				q.pop();
			}
		}
		else if (commend == "size") { cout << q.size() << "\n"; }
		else if (commend == "empty") { cout << q.empty() << "\n"; }
		else if (commend == "front") {
			if (q.empty()) { cout << "-1\n"; }
			else {cout << q.front() << "\n";}
		}
		else if (commend == "back") {
			if (q.empty()) { cout << "-1\n"; }
			else { cout << q.back() << "\n"; }
		}
	}
	return 0;
}

 

 

cin.tie(0); 와 cin.sync_with_studio(0);는 입출력 시간을 덜어주는 코드이다.

+) 참고 : su-m.tistory.com/7

ios::sync_with_stdio(false), cin.tie(NULL) 사용법과 설명

 

 

버전 4. STL <deque> 사용 (메모리 : 8416KB    시간 : 412ms)

#include <iostream>
#include <deque>
#include <string>
using namespace std;

int main() {
	int N = 0;
	cin >> N;

	deque<int>dq;
	int a = 0;
	string commend = "";

	while (N--) {
		cin.tie(0);
		cin.sync_with_stdio(0);
		cin >> commend;
		if (commend == "push") {
			cin >> a;
			dq.push_back(a);
		}
		else if (commend == "pop") {
			if (dq.empty()) { cout << "-1\n"; }
			else {
				cout << dq.front() << "\n";
				dq.pop_front();
			}
		}
		else if (commend == "size") { cout << dq.size() << "\n"; }
		else if (commend == "empty") { cout << dq.empty() << "\n"; }
		else if (commend == "front") {
			if (dq.empty()) { cout << "-1\n"; }
			else { cout << dq.front() << "\n"; }
		}
		else if (commend == "back") {
			if (dq.empty()) { cout << "-1\n"; }
			else { cout << dq.back() << "\n"; }
		}
	}
	return 0;
}

+) 참고 : hyeonstorage.tistory.com/325

[STL] deque 정리 및 예제