[Deque] 5430 AC (백준)

Deque의 성질을 잘 활용해야 하는 문제.

 

이것을 데크를 무시하고, 리버스를 처음에 그대로 구현했다가.. 시간초과가 났다.

p의 길이의 합과 n의 합이 70만을 넘지 않다는 것이지...

p x n 이 70만을 안 넘는 것은 당연히 아니었다.

 

리버스 있는 그대로 해서 하는 순간 reverse가 O(N)이라고 가정하면,

전체 수행시간이 O(PN)이 되어 10억, 즉 10초 정도로 시간초과가 난다.

 

그래서, 아이디어는

리버스했을 때 front인지 rear인지 설정을하고

각각 pop_front, pop_back을 해주면된다.

 

개념적으로는 참 쉬운데,

문자열 다루는데 익숙하지 않았던지 푸는데 너무 오래걸렸다.

 

string 객체의 substr을 잘 이용해보았다.

string s;
s = "2019.08.28"
int start_pos = 0;
int start_pos = 4;
string new_string = s.substr(start_pos, start_pos)

>> 2019

참고로 string은 append 기능으로 '+' 연산도 지원한다.

 

 

또한 cin, getline(string, cin) 이렇게 문자열을 통째로 받아오는 것을 이용했었는데,

그래서 cin.clear(), cin.ignore(2, '\n'); 등도 필요했었다.

근데 그냥 cin >> T >> p >> n >> s;

편하게 받아오면 된다.

 

 

 

 

아래는 정답 코드이다. 

#include <iostream>
#include <deque>

using namespace std;

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

    int T, n;
    cin >> T;
    cin.clear();
    cin.ignore(2, '\n');
    while(T--){
        string p, string_arr;
        cin >> p >> n >> string_arr;

        deque<int> deq;
        
        if (n != 0){
            int start = 1;
            for (int i=1; i<string_arr.size(); ++i){
                if (string_arr[i] == ',' || string_arr[i] == ']'){
                    deq.emplace_back(stoi(string_arr.substr(start, i - start)));
                    start = i + 1;
                }
            }
        }

        
        bool isFront = true;
        bool isError = false;
        for (int i=0; i<p.size(); ++i){
            if (p[i] == 'R') {
                if (isFront) isFront = false;
                else isFront = true;
            }
            else if (p[i] == 'D') {
                if (deq.empty()) {
                    isError = true;
                    break;
                }
                if (isFront) deq.pop_front();
                else deq.pop_back();
            }
        }

        if (isError) cout << "error\n";
        else {
            if (deq.empty()) cout << "[]\n";
            else {
                int size = deq.size();
                if (isFront){
                    cout << '[' << deq[0];
                    for (int i=1; i<size; ++i) {
                        cout << ',' << deq[i];
                    }
                }
                else {
                    cout << '[' << deq[size - 1];
                    for (int i=size - 2; i>=0; --i) {
                        cout << ',' << deq[i];
                    }
                }
                cout << "]\n";
            }
        }
    }
    return 0;
}