[백준,c++] 5430번 - AC

문제

5430번: AC

 

코드

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

using namespace std;

void parsing(string s, deque<int> &dq){
    istringstream ss(s);
    string stringbuffer;
    while(getline(ss, stringbuffer, ',')){
        dq.push_back(stoi(stringbuffer));
    }
}
int main(){
    int T; cin>>T;
    while(T--){
        string cmd; cin>>cmd;
        int len; string arr; cin>>len>>arr;
        deque<int> dq;
        vector<int>v;
        reverse(arr.begin(), arr.end());
        arr.pop_back();
        reverse(arr.begin(), arr.end());
        arr.pop_back();
        
        parsing(arr, dq);
        bool flag = true, rev = false;
        for(char c: cmd){
            if(c=='D'){
                if(dq.empty()){
                    flag = false;
                    break;
                }
                if(!rev) dq.pop_front();
                else dq.pop_back();
            }
            else if(c=='R'){
                rev=!rev;
            }
        }
        if(!flag) cout<<"error"<<'\n';
        else{
            if(!rev){
                cout<<"[";
                while(!dq.empty()){
                    cout<<dq.front();
                    dq.pop_front();
                    if(dq.size()>=1)cout<<",";
                }
                cout<<"]"<<'\n';;
            }
            else{
                cout<<"[";
                while(!dq.empty()){
                    cout<<dq.back();
                    dq.pop_back();
                    if(dq.size()>=1)cout<<",";
                }
                cout<<"]"<<'\n';;
            }
        }
    }
}

 

풀이

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

using namespace std;

void parsing(string s, deque<int> &dq){
    istringstream ss(s);
    string stringbuffer;
    while(getline(ss, stringbuffer, ',')){
        dq.push_back(stoi(stringbuffer));
    } 
}
int main(){
    int T; cin>>T;
    while(T--){
        string cmd; cin>>cmd;
        int len; string arr; cin>>len>>arr;
        deque<int> dq;
        vector<int>v;
        reverse(arr.begin(), arr.end());
        arr.pop_back();
        reverse(arr.begin(), arr.end());
        arr.pop_back();
        
        parsing(arr, dq);
        bool flag = true;
        for(char c: cmd){
            if(c=='D'){
                if(dq.empty()){
                    flag = false;
                    break;
                }
                dq.pop_front();
            }
            else if(c=='R'){
                reverse(dq.begin(), dq.end());
            }
        }
        if(!flag) cout<<"error"<<'\n';
        else{
            cout<<"[";
            while(!dq.empty()){
                cout<<dq.front();
                dq.pop_front();
                if(dq.size()>=1)cout<<",";
            }
            cout<<"]"<<'\n';;
        }
    }
}

처음 제출했던 코드.. 당연히 for문 내에서 reverse 해줬기 때문에 O(100,000 * 100,000)가 되어서 시간 초과가 나게 됩니다.

시간 초과를 해결하기 위해 rev라는 bool 값을 통해 배열이 뒤집힌 상태인지, 아닌지를 구별해서 rev의 상태에 따라 D연산을 deque의 front에서 제거할 것인지, back에서 제거할 것인지 결정했습니다.

마찬가지로 출력도 rev의 상태에 따라 front 혹은 back에서 출력할지 결정했습니다. 그 외 나머지 부분은 parsing 하는 부분이 조금 까다로웠을 뿐 크게 어렵지는 않은 문제였습니다.