[백준] C/C++ acmicpc_5430 AC

진짜 간단해보였는데, 돌릴때마다 새로운 반례들을 만나면서 생각보다 시간이 오래걸렸다..

알고리즘은 덱 이라는 자료구조를 이용하여 앞에서와 뒤에서 빼는 방식을 사용해야했다. 그렇지 않고 v.erase(v.begin())으로 앞에서 지우면 시간초과가 나왔다. 

그리고reverse할 때, 진짜로 reverse하면 안되고 reverse했을땐 뒤에서, 정방향일 땐, 앞에서 pop해주는 방식으로 해결했다.

주저리 주저리 설명보단 역시 코드로 보는게 빠를듯 하다. 

반례를 여러번 고치다보니 조금 지저분하긴 하다....

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


int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;

	string func;
	int n;
	string list;

	for (int i = 0; i < t; ++i) {
		cin >> func >> n>>list;
		string tmp = list.substr(1, list.size() - 2);
		int startIndex = 0;
		int findIndex = tmp.find(",", startIndex);
		deque<string> dq;
		int error = 0;
		
		while (findIndex != -1) {
			dq.push_back(tmp.substr(startIndex, findIndex - startIndex));
			startIndex = findIndex + 1;
			findIndex = tmp.find(",", startIndex);
		
		}
		dq.push_back(tmp.substr(startIndex));
		
		int is = 1;
		if (n == 0) {
			is = 0;
		}
		int reverse = 0;
	
		for (int j = 0; j < func.size(); ++j) {
			if (dq.empty()) {
				
				is = 0;
			}
			if (func[j] == 'R') {
				if (reverse) {
					reverse = 0;
				}
				else {
					reverse = 1;
				}
			}
			if (func[j] == 'D') {
			
				if (!is) {
					error = 1;
					break;
				}
				else if (reverse) {
					dq.pop_back();
				}
				else {
					dq.pop_front();
				}
			}
		}
		if (error) {
			cout << "error" << '\n';
		}
		else {
			if (dq.empty()) {
				cout << "[]" << '\n';
			}
			else {
				if (!reverse) {
					string answer = "[";
					for (int k = 0; k < dq.size() - 1; ++k) {
						answer += dq[k];
						answer += ",";
					}
					answer += dq[dq.size() - 1];
					answer += "]";

					cout << answer << '\n';
				}
				else {
					string answer = "[";
					for (int k = dq.size()-1; k >0; --k) {
						answer += dq[k];
						answer += ",";
					}
					answer += dq[0];
					answer += "]";

					cout << answer << '\n';
				}
				
			}
		}

	}
}