알고리즘/BOJ
[C++] 백준 5430번 - AC
Jay, Lee
2021. 8. 23. 14:21
생각보다 너무 오래 고민했던 문제
처음에는 vector 계속 sort하는 방법을 생각했지만 그러기에는 메모리 제한에 걸릴 것이다.
그래서 검색을 하다가 deque로 하는 방법이 있어서 이 방법을 채택했다.
stack과 queue는 일방적으로 뒤, 앞에 있는 원소만 다룰 수 있지만,
deque는 앞, 뒤의 원소를 둘 다 다룰 수 있다는 장점이 있다.
그래서 reverse했을 때 계속해서 vector로 reverse sort 해줄 필요 없이
reverse한 것을 체크해서 앞이나 뒤에서부터 원소를 출력해주면 된다.
#include <iostream>
#include <string>
#include <deque>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
bool check, err;
string s, numline;
int n;
while (t--) {
deque<int> dq;
check = true;
err = false;
cin >> s >> n >> numline;
int i = 1;
while (numline[i] != '\0') {
int x = 0;
while (numline[i] >= '0' && numline[i] <= '9') {
x *= 10;
x += int(numline[i] - '0');
i++;
}
if (x != 0) {
dq.push_back(x);
}
i++;
}
i = 0;
while (s[i] != '\0') {
if (s[i] == 'R') {
check = !check;
}
else if (s[i] == 'D') {
if (dq.empty()) {
cout << "error" << "\n";
err = true;
break;
}
if (check) {
dq.pop_front();
}
else {
dq.pop_back();
}
}
i++;
}
if (!err) {
cout << "[";
}
while (!dq.empty()) {
if (check) {
auto c = dq.front();
dq.pop_front();
cout << c;
}
else {
auto c = dq.back();
dq.pop_back();
cout << c;
}
if (!dq.empty())
cout << ",";
}
if (!err) {
cout << "]" << "\n";
}
}
return 0;
}