10866_덱

www.acmicpc.net/problem/10866

10866번: 덱

자료구조 중 하나인 덱을 구현하는 문제이다. 덱 라이브러리를 사용해서 풀어도 되고 직접 풀어도 된다. 나는 라이브러리를 사용했다. 라이브러리를 사용하면 쉽게 풀 수 있다. 

데크는 벡터( vector) 에서 제공하는 많은 기능을 제공해준다. 하지만, 데크의 경우 벡터와는 다르게 양쪽 끝 모두에서 원소의 효율적인 추가와 삭제가 가능하다. 하지만, 벡터와는 달리 데크는 모든 원소가 메모리 상에 연속적으로 존재한다고 보장할 수 없다. 즉, 포인터 연산을 통해서 데크의 원소들을 안전하게 접근할 수 없다는 의미이다.

벡터와 데크 모두 비슷한 인터페이스를 제공하고 있지만, 내부적으로는 다르게 처리된다. 벡터의 경우 capacity 가 꽉 찼을 경우 새롭게 크게 한 덩어리의 메모리를 할당하게 되지만, 데크의 경우메모리 상에서 잘게 쪼개어서 보관하게 된다. 물론, 데크 객체 자체에서 메모리에 쪼개져서 보관되는 덩어리들의 위치를 기억하고, 각각의 원소에 대해 접근할 수 있는 인터페이스를 제공해준다. 따라서 데크는 내부적으로 벡터의 비해 조금 더 복잡하게 구현되어 있지만 그 덕분에 벡터와는 달리 메모리 공간을 효율적으로 사용할 수 있게 된다. 뿐만 아니라 엄청나게 큰 데이터의 경우, 데크는 벡터와는 다르게 많은 양의 메모리 재할당을 하지 않기 때문에 좀더 빠르다고 볼 수 있다.

처음과 끝 말고 중간에 원소의 삽입과 삭제를 빈번하게 사용한다면 데크 보다는 리스트(list)를 사용하는 것을 추천한다.

 

참고 : modoocode.com/176

여기서 조금 까다로운 점은 strsplit를 사용하는 것이다. 나는 split를 사용했는데, 다른 사람의 코드를 참고해보니 cin을 하고 push_back이거나 push_front 일 때만 한 번 더 cin 해주는 식이었다. 너무 어렵게 구현한 듯 싶다. 

strsplit 사용

#include<iostream>
#include<vector>
#include<deque>
#include<string>
#include<sstream>
 
using namespace std;
vector<string> fn_split(string str, char deli){
    vector<string> s_group;
    stringstream ss(str);
    string temp;
 
    while(getline(ss, temp, deli)){
        s_group.push_back(temp);
    }
    return s_group;
}
int main(void){
    int n;
    string s, t;
    deque<int> dq;
    vector<int> ans;
    
    getline(cin, t);
    n = stoi(t);
    for(int i = 0; i < n ;i++){
        getline(cin, s);
        vector<string> line = fn_split(s, ' ');
        if(line.size() > 1){
            if(line[0] == "push_back")
                dq.push_back(stoi(line[1]));
            else if(line[0] == "push_front")
                dq.push_front(stoi(line[1]));
        }else{
            if(line[0] == "front"){
                if(dq.empty()){ans.push_back(-1);continue;}
                ans.push_back(dq.front());
            }else if(line[0] == "back"){
                if(dq.empty()){ans.push_back(-1);continue;}
                ans.push_back(dq.back());
            }else if(line[0] == "empty"){
                ans.push_back(dq.empty());
            }else if(line[0] == "size"){
                ans.push_back(dq.size());
            }else if(line[0] == "pop_front"){
                if(dq.empty()){ ans.push_back(-1);continue;}
                ans.push_back(dq.front());
                dq.pop_front();
            }else if(line[0] == "pop_back"){
                if(dq.empty()){ans.push_back(-1);continue;}
                ans.push_back(dq.back());
                dq.pop_back();
            }
        }
    }
    for(int a : ans)
        cout << a << '\n';
}
 

사용 x

#include<iostream>
#include<vector>
#include<deque>
#include<string>
 
using namespace std;
 
int main(void){
    int n;
    string s, t;
    deque<int> dq;
    vector<int> ans;
 
    cin >> n;
    for(int i = 0; i < n ;i++){
        cin >> s;
        if(s == "push_back"){
            cin >> t;
            dq.push_back(stoi(t));
        }else if(s == "push_front"){
            cin >> t;
            dq.push_front(stoi(t));
        }
        else if(s == "front"){
            if(dq.empty()){ans.push_back(-1);continue;}
            ans.push_back(dq.front());
        }else if(s == "back"){
            if(dq.empty()){ans.push_back(-1);continue;}
            ans.push_back(dq.back());
        }else if(s == "empty"){
            ans.push_back(dq.empty());
        }else if(s == "size"){
            ans.push_back(dq.size());
        }else if(s == "pop_front"){
            if(dq.empty()){ ans.push_back(-1);continue;}
            ans.push_back(dq.front());
            dq.pop_front();
        }else if(s == "pop_back"){
            if(dq.empty()){ans.push_back(-1);continue;}
            ans.push_back(dq.back());
            dq.pop_back();
        }
    }
    for(int a : ans)
        cout << a << '\n';
}
 

시간과 코드를 줄일 수 있었다.