[백준][C++] 5430: AC

문제 링크: https://www.acmicpc.net/problem/5430

 

덱(std::deque)을 쓰거나 투포인터로 푸는 방법이 있겠습니다. 덱의 맨 앞, 뒤에 넣고 빼는 연산은 O(1)의 시간이 걸리는데, 벡터(std::vector)의 경우 맨 앞에 추가할 경우 배열 전체를 한칸씩 뒤로 밀어야 하니 O(n)의 시간이 걸리니 안됩니다.

D 연산도 std::reverse 등으로 구현하면 안됩니다. reverse는 O(n) 시간복잡도를 가지니 안됩니다. bool 변수를 이용하는게 낫습니다.

 

예외처리를 좀 꼼꼼히 해줘야 되는 문제입니다. 빈 배열을 입력받을 때라든지, 빈 배열에서 D나 R을 수행할 때 체크를 잘 해줘야 합니다.

#include <bits/stdc++.h>
using namespace std;

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

	int t;
	cin >> t;
	while (t--) {
		string p;
		int n;

		cin >> p >> n;

		char ign;
		deque<int> dq(n);
		cin >> ign;
		for (auto& c : dq) {
			cin >> c >> ign;
		}
		if (!n) cin >> ign;

		bool rev = false;
		bool err = false;
		for (auto& ch : p) {
			if (ch == 'R') rev ^= 1;
			else {
				if (dq.empty()) {
					err = true;
					break;
				}

				if (rev)
					dq.pop_back();
				else
					dq.pop_front();
			}
		}

		if (err)
			cout << "error\n";
		else {
			cout << "[";
			if (rev) {
				for (auto rit = dq.rbegin(); rit != dq.rend(); ++rit) {
					cout << *rit;
					if (rit + 1 != dq.rend())
						cout << ",";
				}
			}
			else {
				for (auto it = dq.begin(); it != dq.end(); ++it) {
					cout << *it;
					if (it + 1 != dq.end())
						cout << ",";
				}
			}
			cout << "]\n";
		}
	}

	return 0;
}