C++ 2020. 2. 6. 21:53

[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

I wanted to know if someone knew the implementation of the C++ string::erase function and it's complexity. I know the C++ string is an object of characters. I'm assuming it doesn't allocate and cr...

stackoverflow.com

위 링크에 있는 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/

'C++' 카테고리의 다른 글

[C++] 공백 문자도 입력받는 함수 getline 문법 정리  (0) 2020.01.16
'C++' 카테고리의 다른 글
  • [C++] 공백 문자도 입력받는 함수 getline 문법 정리
개발자 이우진
이우진 기술 블로그
  • All (86)
    • Spring Framework (20)
    • MSA (7)
      • Event Driven Architecture (3)
    • Java (3)
    • Flink (2)
    • Computer Science (9)
      • Object Oriented Programming (3)
    • Problem Solving (15)
    • Design Pattern (0)
    • React (4)
    • Javascript (2)
    • Web (3)
    • Tools & Environment (3)
    • C++ (2)
    • misc (5)
    • Essay (3)
      • 기술 회고 (5)
  • 홈
  • 태그
  • 관리자
  • 글쓰기
hELLO · Designed By 정상우.v4.2.2
[C++] std::string 클래스가 std::list보다 느릴 수 있는 이유
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.