[C++] std::string 클래스가 std::list보다 느릴 수 있는 이유

백준 1406번 <에디터> 문제(boj.kr/1406)

 

입력한 문자열을 조작하는 문제이고, 같은 문제집에 있던 문제들을 std::string으로 풀어서 처음에는 이 문제를 아래와 같이 쉽게 풀었다.

#include <iostream>
#include <string>

using namespace std;

bool MoveCursor(int& cursor, int str_length, int value) {
    int end = str_length;
    int new_cursor = cursor + value;

    if(new_cursor >= 0 && new_cursor <= end) {
        cursor = new_cursor;
        return true;
    }
    else {
        return false;
    }
}

int main() {
    string str;

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> str;

    int num_operations;
    char operation = 0;
    char parameter = 0;
    cin >> num_operations;

    int length = str.length();
    int cursor = length;

    for(int i=0; i<num_operations; i++) {
        cin >> operation;

        switch (operation)
        {
        case 'L':
            MoveCursor(cursor, length, -1);
            break;
        case 'D':
            MoveCursor(cursor, length, 1);
            break;
        case 'B':
            if(MoveCursor(cursor, length, -1)) {
                str.erase(str.begin() + cursor);
                length--;
            }
            break;
        case 'P':
            cin >> parameter;
            if(cursor == length) {
                str.append(1, parameter);
            }
            else {
                str.insert(cursor, 1, parameter);
            }
            length++;
            MoveCursor(cursor, length, 1);
            break;
        default:
            break;
        }
    }

    cout << str << "\n";

    return 0;
}

결과는 시간 초과였다. 반복문 안에 length()가 시간을 잡아먹는 줄 알아서 length를 직접 계산했지만 여전히 시간 초과가 났다. 나중에 답안을 검색해 보니 list를 활용한 풀이가 나왔다. 나는 std::string을 과대평가해서 틀린 것이다.

 

https://stackoverflow.com/questions/52866539/c-time-and-space-complexity-of-string-class-erase-member-function

C++ Time and Space Complexity of string class erase member function

위 링크에 있는 stackoverflow의 답변을 참고하면, std::string을 포함한 표준 라이브러리는 복잡도를 명시하지 않는다고 한다. 그래서 처음에 cplusplus.com 등을 뒤져봐도 관련 내용을 찾을 수 없었다. 대신 일반적인 상황에서는 vector<char>와 비슷하게 동작한다고 설명한다. 즉, string도 vector처럼 길이가 변할 수 있는 배열 자료구조이다. 따라서, 하나의 문자를 맨 마지막에 삽입/삭제하는 경우는 복잡도가 적겠지만 문자열의 처음과 중간에 삽입/삭제하는 경우라면 O(N) 시간이 걸린다. 배열의 사이즈를 늘리고 뒤에 있는 문자들을 밀어야 하기 때문이다. 내가 작성한 코드에서는 O(N) 시간인 insert()와 erase()가 반복문 안에 있어서 시간이 초과되었을 것이다.

 

그래서 이 문제는 문자열 중간에 삽입/삭제가 빈번하게 일어나니 배열과 유사한 std::string 보다는 Doubly Linked List 자료구조인 std::list가 더욱 유리하다. Doubly linked list에서 삽입/삭제 함수인 insert()와 erase()는 시간 복잡도가 O(1)이다. 노드 하나를 새로 할당하고 포인터만 연결해 주면 되기 때문이다. 따라서 이 문제는 list<char>을 이용하여 풀면 수행시간이 줄어든다. list의 생성자중 iterator를 파라미터로 받는 것이 있기 때문에 string을 쉽게 list로 변환할 수 있다. cursor도 int에서 iterator type으로 바꾸면 삽입/삭제 위치를 동작을 수행할 때 마다 탐색하지 않고, iterator 그 자체로 위치를 pointer처럼 저장할 수 있다.

 

[참고] string 메소드의 시간 복잡도(추정)

https://www.hackerearth.com/practice/notes/standard-template-library/