[백준 5430] AC (C++)

#include <cstring>
#include <deque>
#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

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

    int t;
    cin >> t;

    for (int i = 0; i < t; i++) {
        string func;
        cin >> func;

        int n;
        cin >> n;

        // 문자열로 이루어진 배열을 입력받고 숫자만 파싱
        string arr;
        cin >> arr;

        
        string temp;
        deque<int> nums;

        // 앞뒤의 대괄호를 삭제한다
        arr = arr.substr(1);
        arr = arr.substr(0, arr.size() - 1);

        istringstream ss(arr);

        while (getline(ss, temp, ',')) {
            nums.push_back(stoi(temp));
        }

        // 함수를 하나씩 실행한다
        for (int j = 0; j < func.size(); j++) {
            if (func[j] == 'R') {
                // 수 뒤집기
                deque<int> temp;
                while (!nums.empty()) {
                    temp.push_back(nums.back());
                    nums.pop_back();
                }
                nums = temp;
            }
            else {
                // 맨 앞 단어 뽑기
                if (nums.empty()) {
                    cout << "error" << "\n";
                    break;
                }
                else {
                    nums.pop_front();
                }
            }
        }

        if (nums.empty()) {
            continue;
        }
        else {
            cout << "[";
            for (int n = 0; n < nums.size(); n++) {
                cout << n;

                if (n < nums.size() - 1) {
                    cout << ",";
                }
            }
            cout << "]\n";
        }

    }
}

처음에 작성한 코드는 시간초과가 나왔다. 문제는 바로 R커맨드가 입력되면 덱 반전을 위해 temp라는 deque에 역으로 데이터를 집어넣는 부분인데 R이 많이 수행될수록 실행시간은 기하급수적으로 증가하게 된다.

그래서 해결 방법으로, R이 입력될 때마다 isRev라는 bool변수를 계속 스위칭함으로써 D가 입력되면 false일때 덱의 뒤에서, true일때 덱의 앞에서 데이터를 삭제하도록 변경하였다.

또, 텅빈 배열 []를 주고, RRRRRRRRRR이 입력되는 경우 오류가 없으므로 []처럼 빈 배열이 출력되어야 하지만, 출력이 아무것도 나오지않는 문제가 있었다. 이 문제를 해결하기 위해 isError라는 bool변수를 하나 더 두기로 하였다. D라는 커맨드가 입력될 때만 error 문구가 나올 수 있으므로 D가 입력될 때 덱이 텅 비어있으면 isError를 true로 바꿔준다.

위 2개의 해결방법을 적용하면, 덱 반전 수행은 출력부분에서 단 한 번 수행하게 되고, error가 발생하지 않으면 빈 배열 []을 출력할 수 있게된다.