백준 5430번: AC

[문제 링크]

5430번: AC

---

문자열과 관련된 구현 문제였다.

문자열의 길이가 최대 100,000이기 때문에 뒤집기 연산을 할 때 실제 문자열을 뒤집으면 시간 복잡도가 너무 커지게 된다.

따라서 뒤집기 연산을 할 때마다 isReversed 변수를 토글하여 현재 뒤집힌 상태인지 아닌지를  저장하고,

버리기 연산을 하게 될 경우 현재 뒤집히지 않은 상태라면 앞에서 숫자를 빼고, 뒤집힌 상태라면 뒤에서 숫자를 빼는 방식으로 구현하였다.

앞, 뒤에서 자유롭게 원소를 넣고 빼는 연산을 수행하기 위해 자료구조는 Deque를 사용하였다.

 

마지막으로 문자열을 출력하는 연산에서는

뒤집히지 않은 상태라면 Deque의 앞에서부터 하나씩 그대로 출력해주면 되며,

뒤집힌 상태일 경우 Deque의 뒤에서부터 하나씩 빼는데 그대로 출력하면 숫자가 뒤집혀서 출력되기 때문에 숫자를 임시로 저장하는 Stack 컨테이너에 옮겨 담아서 출력하였다.

---

#include <iostream>
#include <vector>
#include <stack>
#include <deque>
using namespace std;

void printAC(string acStr, string func) {
	deque<char> dq;
	for (auto x : acStr)
		dq.push_back(x);

	dq.pop_front();
	dq.pop_back();

	bool isReversed = false;

	for (auto x : func) {
		if (x == 'R')
			isReversed = !isReversed;
		else {
			if (dq.empty()) {
				cout << "error";
				return;
			}

			char hereChar;
			if (!isReversed) {
				hereChar = dq.front();
				dq.pop_front();

				while (!dq.empty() && hereChar != ',') {
					hereChar = dq.front();
					dq.pop_front();
				}

			}
			else {
				hereChar = dq.back();
				dq.pop_back();

				while (!dq.empty() && hereChar != ',') {
					hereChar = dq.back();
					dq.pop_back();
				}

			}
		}
	}

	char hereChar;

	cout << '[';
	if (!isReversed) {
		while (!dq.empty()) {
			hereChar = dq.front();
			dq.pop_front();

			cout << hereChar;
		}
	}
	else {
		stack<char> tempStk;
		while (!dq.empty()) {
			hereChar = dq.back();
			dq.pop_back();

			if (hereChar != ',')
				tempStk.push(hereChar);
			else {
				while (!tempStk.empty()) {
					cout << tempStk.top();
					tempStk.pop();
				}
				cout << hereChar;
			}
		}
		while (!tempStk.empty()) {
			cout << tempStk.top();
			tempStk.pop();
		}
	}
	cout << ']';
}

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int tc;
	cin >> tc;

	while (tc--) {
		string func;
		cin >> func;

		int n;
		cin >> n;

		string acStr;
		cin >> acStr;

		printAC(acStr, func);
		cout << '\n';
	}

	return 0;
}