[백준 5430번] AC

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

5430번: AC

문제 풀이

 

[주의 1]

R 연산을 할 때마다 reverse 함수를 사용하면 시간 초과가 납니다.

왜냐하면

reverse 함수가 O(N)의 시간복잡도가 걸리니깐

전체 O(n * len(p))의 시간복잡도가 걸립니다.

p의 길이가 0 <= len(p) <= 100,000,

n의 범위가 0 <= n <= 100,000 이므로

만약에 p가 전부 R로 이루어져 있고, n = 100,000 이면

O(10^5 * 10^5) = O(10^10)이 되니깐 시간제한 1초 안에 해결할 수 없습니다.

[주의 2]

빈 배열에서 R연산을 해도 error가 아니다

 

 

reverse 함수를 사용하지 않고 R연산을 구현하는 방법은

deque를 사용하면 됩니다.

 

D연산을 배열의 앞과 뒤에서 할 수 있는데

처음엔 앞에서 시작해서 R연산을 할 때마다 앞, 뒤를 바꿔주면 됩니다.

 

<c++ 소스 코드> deque 덱, 자료구조

#include <iostream>
#include <deque>
#include <string>
#include <vector>
using namespace std;
 
//false return is error
bool solve(deque<int> &x, string& p, bool& flag) {
    flag = true; //true = queue, false = stack
    for (auto& c : p) {
        if (c == 'R') flag = !flag;
        else if (c == 'D' && x.empty()) {
            return false;
        }
        else if (c == 'D' && flag) { //queue
            x.pop_front();
        }
        else if (c == 'D' && !flag) { // stack
            x.pop_back();
        }
    }
    return true;
}
void print_x(bool flag, deque<int> &x) {
    if (flag) { //queue
        cout << '[';
        while (!x.empty()) {
            cout << x.front(); x.pop_front();
            if(!x.empty())cout << ',';
        }
        cout << ']';
    }
    else { //stack
        cout << '[';
        while (!x.empty()) {
            cout << x.back(); x.pop_back();
            if (!x.empty())cout << ',';
        }
        cout << ']';
    }
    cout << '\n';
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int test_case; cin >> test_case;
    while (test_case--) {
        string p; cin >> p;
        int n; cin >> n;
        string s; cin >> s;
        deque<int> x;
        string num;
        s.erase(s.begin());
        for (auto& c : s) {
            if (c == ',' || c == ']' && num.size()) {
                x.push_back(stoi(num));
                num.clear();
            }
            else if (c >= '0' && c <= '9') {
                num.push_back(c);
            }
        }
        bool flag = true;
        if (solve(x, p, flag)) {
            if (flag) print_x(true, x);
            else print_x(false, x);
        }
        else {
            cout << "error\n";
        }
 
    }
    return 0;
}