BOJ 10866번 :: 덱

#문제

https://www.acmicpc.net/problem/10866

10866번: 덱

 

#작성 코드

#include <iostream>
using namespace std;
 
typedef class dequeue{
    private:
    const int f=0;        // 데이터 들어있는 제일 앞 위치 가리킴 
    int b =0;        // 데이터가 들어있는 제일 뒤 다음자리 가리킴 
    int data[10000];
    public:
    void push_front(int x){
        if( b==0 ){
            data[0] = x;
            b = 1;
        }
        else{
            // 한칸씩 데이터 밀고 
            for(int i=b; i>f; i--){
                data[i] = data[i-1];
            }
            data[0] = x;
            b++;
        }
    }
    void push_back(int x){
        if( b==0 ){
            data[0] = x;
            b=1;
        }
        else{
            data[b] = x;
            b++;
        }
    } 
    void pop_front(){
        if( b==0 ){
            cout<<-1<<'\n';
            return;
        }
        else{
            cout<<data[f]<<'\n';
            for(int i=f; i<b; i++){
                data[i] = data[i+1];
            }
            b--;
        }
    }
    void pop_back(){
        if( b==0 ){
            cout<<-1<<'\n';
        }
        else{
            cout<<data[b-1]<<'\n';
            b--;
        }
    }
    void size(){
        cout<<b<<'\n';
    }
    void empty(){
        if( b==0 ) cout<<"1\n";
        else cout<<"0\n";
    }
    void front(){
        if( b==0 ) cout<<"-1\n";
        else cout<<data[f]<<'\n';
    }
    void back(){
        if( b==0 ) cout<<"-1\n";
        else cout<<data[b-1]<<'\n';
    }
}dequeue;
int main(){
    dequeue dq;
    int n;
    cin>>n;
    for(int i=0; i<n; i++){
        string s;
        cin>>s;
        if( s=="push_front" ){
            int x;
            cin>>x;
            dq.push_front(x);
        }else if( s=="push_back" ){
            int x;
            cin>>x;
            dq.push_back(x);
        }else if( s=="pop_front" ){
            dq.pop_front();
        }else if( s=="pop_back"){
            dq.pop_back();
        }else if( s=="size"){
            dq.size();
        }else if( s=="empty"){
            dq.empty();
        }else if( s=="front"){
            dq.front();
        }else if( s=="back"){
            dq.back();
        }
    }
    return 0;
}

##

AC판정을 받긴 했지만, 데이터를 front에 넣고 뺄때마다 dequeue에 들어있는 data를 인덱스 0에서부터 시작하도록 밀어줬더니 시간이 생각보다 오래 걸렸다.(296ms)

dequeue에 넣을 수 있는 최대 데이터 수를 정해놓고 ex)10,000,000개. front_idx와 back_idx를 사용해서 관리를 하면 front에 push, pop하는 연산 시간을 줄일 수 있겠지!

 

더 정확히 dequeue를 구현하려면 연결리스트를 이용해서,

Node에 int data, Node* next를 저장할 수 있는 Node 구조체를 만들고

Node* front, back으로 관리하면 front에서 push/pop하는 오버헤드가 훨씬 작겠지!