백준[5430] AC

문제 설명

문제 링크

http://icpc.me/5430

5430번: AC

풀이

덱을 이용하여 풀이 할 수 있다.

배열을 뒤집을 때, 진짜로 배열을 뒤집게 된다면 이때 시간복잡도가 O(n)이기 때문에 O(np)가 되어 터지게 된다.

그렇기 때문에 배열을 뒤집었는지 여부를 체크하여 수를 앞에서 버릴지 뒤에서 버릴지 정해야한다.

코드

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

void solve() {
    deque<int> dq;
    string cmd; cin >> cmd;
    int n; cin >> n;
    string inp; cin >> inp;
    string num;
    for (const auto &c : inp) {
        if (c == '[' || c == ']') continue;
        if (c == ',') {
            dq.push_back(stoi(num));
            num.clear();
        } else {
            num.push_back(c);
        }
    }
    if (num.length()) dq.push_back(stoi(num));

    bool rev = false;
    for (const auto &c : cmd) {
        if (c == 'R') {
            rev = !rev;
        } else {
            if (!dq.size()) {
                cout << "error\n";
                return;
            }
            if (!rev) dq.pop_front();
            else dq.pop_back();
        }
    }
    cout << "[";
    if (rev && dq.size()) {
        for (int i = dq.size() - 1; i > 0; i--) cout << dq[i] << ",";
        cout << dq[0];
    }  else if (!rev && dq.size()) {
        for (int i = 0; i < dq.size() - 1; i++) cout << dq[i] << ",";
        if (dq.size()) cout << dq[dq.size() - 1];
    }
    cout << "]\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
}