[BOJ] 5430 : AC

5430 : AC

풀이

DEQUE

[1,2,3] 이런식으로 숫자가 들어와서 문자열 처리하는것도 까다로웠다.

scanf로 한문자씩 받고 ,와 []는 따로 처리했다.

그다음은 Reverse할때인데, 덱을 하나더만들어서 옮겼더니 시간초과가 났다.

‘큐를 직접 뒤집지 말고, R마다 front, back 방향만 switching해주자’

란 아이디어로 시간초과를 해결했다.

시간을 많이 줄일 수 있는 덱의 활용도를 알게되었다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <cstdio>
using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        //큐를 직접 뒤집지 말고, R마다 front, back 방향만 switching해주자
        int swit = 1;
        deque<int> dq;
        string a;
        cin>>a;
        int n;
        cin>>n;
        char trash;
        scanf("\n%c",&trash);
        for(int i=0;i<n;i++){
            int tmp;
            scanf("%d",&tmp);
            dq.push_back(tmp);
            scanf("%c",&trash);
        }
        if(n==0)
            scanf("%c",&trash);
        int flag=0;
        for(int i=0;i<a.size();i++){
            if(a[i]=='R'){
                if(swit)
                    swit=0;
                else
                    swit=1;
            }else if(a[i]=='D'){
                if(dq.empty()){
                    flag=1;
                    break;
                }
                if(swit)
                    dq.pop_front();
                else
                    dq.pop_back();
            }
        }
        //출력
        if(flag){
            cout<<"error"<<'\n';
        }else{
            cout<<'[';
            if(swit){
                if(!dq.empty()){
                    cout<<dq.front();
                    dq.pop_front();
                }
                while(!dq.empty()){
                    cout<<',';
                    cout<<dq.front();
                    dq.pop_front();
                }
            }
            else{
                if(!dq.empty()){
                    cout<<dq.back();
                    dq.pop_back();
                }
                while(!dq.empty()){
                    cout<<',';
                    cout<<dq.back();
                    dq.pop_back();
                }
            }
            cout<<']'<<'\n';
        }
    }
    return 0;
}

Written on March 17, 2019