[백준 5430번 / C++] AC

dequeue 자료구조를 활용하자. 

 

dequeue를 활용하지 않고 벡터를 활용하여 R이라는 명령어가 들어왔을 때 reverse라는 정렬을 할 수도 있다. 하지만 수행할 함수가 100,000이면서 R이라는 명령어만 주어졌고, n의 개수가 100,000이라면 100억번을 수행해야한다. 그렇다면 시간초과가 발생하게 된다. 또한, D라는 명령어가 들어왔을 때는 맨 앞에 원소를 지우는 erase 함수를 수행할 수 있지만 뒤에 있는 모든 원소를 하나씩 당겨와야하기 때문에 그만큼의 시간이 든다.

 

그렇기 때문에 dequeue라는 자료구조를 활용해서 제일 앞의 원소를 뺄지 또는 제일 끝의 원소를 뺄지를 back이라는 비트변수가 체크해준다. 

 

즉, R이라는 명령어가 들어오면 back라는 변수를 1로 세팅하면서 현재 거꾸로 정렬된다고 가정을 한다는것이다. 

이후 D라는 명령어가 들어오면 현재 뒤집혀진 상태로 가정을 하였으니 맨 앞 원소를 빼는것이 아니라, 맨 끝의 원소를 빼면 되는것이다. 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <deque>
using namespace std;
deque <int> q; 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n; cin >> n;
	while (n--) {
		string func;
		cin >> func;
		int num; cin >> num;
		string s; cin >> s;
		string temp = "";
		vector<int> v;
		for (int i = 1; i < s.size() - 1; i++) {
			if (s[i] >= '0' && s[i] <= '9')temp += s[i];
			else {			
				q.push_back(stoi(temp)); 
				temp = "";
			}
		}	
		if (temp.size())q.push_back(stoi(temp)); 
		int flag = 0;
		int back = 0;
		for (int i = 0; i < func.size(); i++) {
			if (func[i] == 'R') {
				if (back)back = 0;
				else back = 1;
			}
			else {
				if (num) {
					if (!back)q.pop_front();
					else q.pop_back();
				}
				else {
					flag = 1;
					cout << "error" << endl;
					break;
				}
				num--; 
			}
		}
		if (!flag) {			
			cout << "["; 
			while (!q.empty()) {
				if (back) {
					cout << q.back(); 
					q.pop_back(); 
				}
				else {
					cout << q.front(); 
					q.pop_front(); 				
				}
				if (!q.empty())cout << ","; 
			}
			cout << "]" << endl; 
		}
	}
}

5430번: AC