BOJ 5430 - AC

www.acmicpc.net/problem/5430

5430번: AC

 

덱을 사용해서 풀었던 문제다.

역으로 뒤집을때, algorithm 헤더의 reverse 함수를 쓰면 시간초과가 발생한다

reverse 의 시간복잡도가 O(N) 이기 때문이다.

뒤집는것 대신에, bool 변수를 이용해서 뒤집혔는지 여부를 파악하고

뒤집히지 않았으면 앞에꺼를 빼는 pop_front() 를 하고 

뒤집혔으면 뒤에꺼를 빼는 pop_back() 을 한다.

그리고 비어있는 덱에서 빼려고 할때, 에러임을 나타내는 bool 변수를 하나 만들어서 체크한다

명령어를 다 수행한뒤, 뒤집힌 상태라면 역순으로 출력하고 아니면 원래 순서대로 출력한다.

 

- c++

 

#include <deque>
#include <iostream>
#include <string>
 
using namespace std;
 
int t, n;
deque<int> dq;
string func, arr;
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        cin >> func;
        cin >> n;
        cin >> arr;
        
        string temp;
        for (int i = 0; i < arr.length(); ++i) {
            if ((arr[i] == '[' || arr[i] == ',' || arr[i] == ']') && !temp.empty()) {
                int num = stoi(temp);
                dq.push_back(num);
                temp.clear();
            } else if ('0' <= arr[i] && arr[i] <= '9') {
                temp.push_back(arr[i]);
            }
        }
        
        bool is_reverse = false;
        bool is_error = false;
        for (int i = 0; i < func.length(); ++i) {
            if (func[i] == 'R') is_reverse = !is_reverse;
            else if (!dq.empty() && func[i] == 'D' && !is_reverse) dq.pop_front();
            else if (!dq.empty() && func[i] == 'D' && is_reverse) dq.pop_back();
            else if (func[i] == 'D' && dq.empty()) is_error = true;
        }
                    
        if (is_error) cout << "error\n";
        else {
            if (is_reverse) {
                cout << "[";
                while(!dq.empty()) {
                    cout << dq.back();
                    dq.pop_back();
                    if (!dq.empty()) cout << ",";
                }
                cout << "]\n";    
            } else {
                cout << "[";
                while(!dq.empty()) {
                    cout << dq.front();
                    dq.pop_front();
                    if (!dq.empty()) cout << ",";
                }
                cout << "]\n";
            }
        }
    }
    
    return 0;
}