[C++] std::list 에서 std::advance / 백준 1406번 에디터

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

1406번: 에디터

백준 1406번 에디터 문제를 풀면서 배열보단 삽입삭제가 O(1)인 리스트를 사용하는게 나을거같아 std::list를 사용했다.

그런데 시간 초과가 계속 나왔다.

나중에 알았지만 std::list에 대해서 제대로 모르고 사용하고있던 터라 insert와 erase 를 제대로 사용하지못했고 std::advance를 이용해 작성했는데 왜 시간초과가 나오는지 이해가 안갔다.

#include <iostream>
#include <list>
#include <cmath>
#include <string>
#include <iterator>

int main(void){
    std::ios_base::sync_with_stdio(false);
    //std::cin.tie(NULL);
    
    
    std::string input;
    std::getline(std::cin, input);
    int cursor = input.length();
    int length = input.length();
    std::list<char> edit_string(input.length());
    {
        int i=0;
        for(auto& ch : edit_string){
            ch = input[i++];
        }
    }
    int N = 0;
    
    std::cin >> N;
    //std::list<char>::iterator range_it;
    std::list<char>::iterator range_backit;
    bool is_backing = false;
    for(int i=0; i<=N; ++i){
        std::getline(std::cin, input);
        
        if (input[0] != 'B' && is_backing){
            auto it = edit_string.begin();
            std::advance(it, cursor);
            edit_string.erase(it, range_backit);
            is_backing =false;
        }
        switch(input[0]){
            case 'L':
                if(cursor > 0){
                    --cursor;
                }
                break;
            case 'D':
                if(cursor < length){
                    ++cursor;
                }
                break;
            case 'B':
                if(cursor > 0){
                    if(!is_backing){
                        range_backit = edit_string.begin();
                        std::advance(range_backit, cursor);
                        is_backing = true;
                    }
                    --cursor;
                    --length;
                    //auto it = edit_string.begin();
                    //std::advance(it, cursor);
                    //edit_string.erase(it);
                }
                break;
            case 'P':
                if (cursor == length){
                    ++cursor;
                    edit_string.push_back(input[2]);
                    ++length;
                }else{
                    auto it = edit_string.begin();
                    std::advance(it, cursor++);
                    edit_string.insert(it, input[2]);
                    ++length;
                }
                break;
        }
    }
    
    if (input[0] != 'B' && is_backing){
            auto it = edit_string.begin();
            std::advance(it, cursor);
            edit_string.erase(it, range_backit);
            is_backing =false;
    }
    for(auto& ch : edit_string){
        std::cout << ch;
    }
    std::cout << "\n";
    return 0;
}

 [잘못된 코드]

 

처음엔 iterator를 지역변수로 계속 사용해서 생기는 문제라고 착각했다. 물론 이게 약간의 시간 지연을 주긴 하겠지만, sizeof를 이용해 사이즈를 측정해보니 8byte였고 이정도면 복사과정에서 많은 시간지연을 잡아먹지 않을것이다.

문제는 std::advance였다.

https://modoocode.com/223#page-heading-6

씹어먹는 C++ - <10 - 1. C++ STL - 벡터(std::vector), 리스트(list), 데크(deque)>

이 블로그에서 보면 std::list 의 iterator의 타입은 BidirectionalIterator 로 한칸씩밖에 못움직이는 반복자이다.

아마도 내 추측에 std::advance(it, 1000)을 하면 메모리 주소 + 1000이 아닌 1000번을 일일히 움직이는것 같다.

따라서 속도저하가 일어났고 시간초과가 나왔다.

좀더 눈에보이는 결과를 보기위해 그냥 insert 와 advance를 이용한 insert를 비교해봤다.

 

#include <iostream>
#include <list>
#include <cmath>
#include <string>
#include <iterator>
#include <chrono>

int main(void){
    std::ios_base::sync_with_stdio(false);
    //std::cin.tie(NULL);
    
    std::list<int> me;
    
    for(int i=0; i<100000;++i){
        me.push_back(i);
    }
    
    auto start = std::chrono::system_clock::now();
    
    auto it = me.begin();
    std::advance(it, 1000);
    for(auto it = me.begin(); it != me.end(); ++it){
        me.insert(it, 10);
    }
    std::chrono::duration<double> sec = std::chrono::system_clock::now() - start;
    std::cout << sec.count() << "\n";
    auto for_it = me.begin();
    start = std::chrono::system_clock::now();
    for(int i=0; i<100000; ++i){
        
        std::advance(for_it, 1000);
        me.insert(for_it, 10);
        for_it = me.begin();
        
    }
    sec = std::chrono::system_clock::now() - start;
    std::cout << sec.count() << "\n";
    return 0;
}

구름ide에서 작성했으며 다른 요인을 감수하고 보더라도 

advance를 이용한 insert가 약 0.7초 더 느렸다. 엄청난 차이.

 

또 이거 말고도 잘못 생각하고 있던점들이 있었는데, insert와 erase.

std::list는 삽입 제거후 iterator가 보존된다.

std::list<int> my_list 에 1,2,3이 담겨있었고 현재 std::list<int>::iterator it 이 3을 가리키고 있을때

4를 가지고있는 노드를 insert를 하면 1,2,4,3 이된다.

하지만, it은 여전히 3을 가리키고 있는다. (4가 아니라)

 

erase도 똑같다. 사라진 노드를 가리키고있는다.

그래서 반환된 반복자를 다시 현재의 반복자에 대입해줘야된다.

모두반영하면 이렇게 짤수 있다.

#include <iostream>
#include <list>
#include <cmath>
#include <string>
#include <iterator>

int main(void){
    std::ios_base::sync_with_stdio(false);
    //std::cin.tie(NULL);
    
    
    std::string input;
    std::getline(std::cin, input);
    std::list<char> edit_string(input.length());
    {
        int i=0;
        for(auto& ch : edit_string){
            ch = input[i++];
        }
    }
    auto cursor = edit_string.end();
    int N = 0;
    
    std::cin >> N;
    
    for(int i=0; i<=N; ++i){
        std::getline(std::cin, input);
        
        switch(input[0]){
            case 'L':
                if(cursor != edit_string.begin()){
                    cursor--;
                }
                break;
            case 'D':
                if(cursor != edit_string.end()){
                    cursor++;
                }
                break;
            case 'B':
                if(cursor != edit_string.begin()){
                    cursor--;
                    cursor = edit_string.erase(cursor);
                }
                break;
            case 'P':
                edit_string.insert(cursor, input[2]);
                break;
        }
    }
    
    //std::cout << edit_string.size();
    for(auto& ch : edit_string){
        std::cout << ch;
    }
    std::cout << "\n";
    return 0;
}

[최종코드]

 

평소 다루지않았던 std::list에 대해 그래도 좀 깊이 안거같아서 나쁘지않은듯