에디터 //1406

• 문제
  
  
  //시간 제한: 0.3초 , 메모리 제한: 512MB

• 입력
  첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

• 출력
  첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

// Created by dongwan-kim on 2022/07/22.
#include<iostream>
#include<list>
#include<string>

using namespace std;

list<char> l;
list<char>::iterator iter;
string s;
int t;
char cmd, c;

int main() {
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        l.push_back(s[i]);
    }
    iter = l.end();
    cin >> t;
    while (t--) {
        cin >> cmd;
        if (cmd == 'L') {
            if (iter != l.begin())
                iter--;
        }
        if (cmd == 'D') {
            if (iter != l.end())
                iter++;
        }
        if (cmd == 'B') {
            if (iter != l.begin()) {
                iter = l.erase(--iter);
            }
        }
        if (cmd == 'P') {
            cin >> c;
            l.insert(iter, c);
        }
    }

    for (iter = l.begin(); iter != l.end(); iter++)
        cout << *iter;
}

풀이

처음 이 문제를 접근할 때 시간 제한 0.3초가 신경쓰이긴 했지만 string에서의 삽입 삭제 시간복잡도를 몰라서 그냥 string으로 받아서 int형 커서를 만들어 문제를 풀었었다. 결과는 예상대로 시간 초과였다.

이후 삽입,삭제의 시간복잡도가 빠른 것을 고민하다가 list를 떠올렸고, 구현하는 것은 그리 오래걸리지 않았다.

새로 알게 된 것으로 list에서 erase는 삭제한 원소의 다음 원소를 가르키는 iterator를 반환한다는 사실을 알게되었다.
insert 또한 삽입한 원소의 iterator를 반환한다.
이 사실을 알고 문제를 푸니 이 문제는 list의 완전 기본 문제임을 알 수 있었다.