[BOJ/C++] 에디터(1406번)

1. 개요

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

1406번: 에디터

1-1. 설명

한 줄로 된 간단한 에디터를 구현한다. 이 편집기는 영어 소문자를 기록할 수 있는 편집기로, 최대 600,000 글자까지 입력 가능하다. 편집기에 대한 각 기능은 위의 링크를 참고한다. 우리는 모든 명령어가 이루어진 후 결과를 출력하는 프로그램을 구현한다. 

1-2. 제한 사항

 - 첫 줄에는 문자열이 주어지며, 문자열의 길이는 N이고 영어 소문자로만 이루어짐

 - N은 100,000 길이를 넘지 않음

 - 둘째 줄에는 입력할 명령어 개수 M이 주어지며, M은 1 이상 500,000 이하

 - 셋째 줄부터 M개의 줄에 거쳐 입력할 명령어 수가 주어짐

---

2. 구현

2-1. 풀이

처음에는 단순히 string을 받아 커서를 통해 insert와 erase를 진행하였으나, 0.3초라는 시간 제한으로 인해 시간초과가 나게 되었다. list를 단순히 사용해도 된다는 글에 list를 이용하여 풀었다. list는 삽입/삭제 시 O(1)의 시간 복잡도를 가지므로, 시간 초과가 나지 않았음을 알게 되었다.

2-2. 코드 

#include <iostream>
#include <string>
#include <list>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string str;
    char commend1, commend2;
    int M;
    list<char> word;

    cin >> str;
    for (int i = 0; i < str.size(); i++) word.push_back(str[i]);
    cin >> M;
    list<char>::iterator iter = word.end();

    for (int i = 0; i < M; i++) {
        cin >> commend1;
        if (commend1 == 'L' && (iter != word.begin())) iter--;
        else if (commend1 == 'D' && (iter != word.end())) iter++;
        else if (commend1 == 'B' && (iter != word.begin())) {
            iter = word.erase(--iter);
        }
        else if (commend1 == 'P') {
            cin >> commend2;
            word.insert(iter, commend2);
        }
    }
    
    for (iter = word.begin(); iter != word.end(); iter++) cout << *iter;
    return 0;
}