[백준] 1406 에디터(C++)

1406번: 에디터 (acmicpc.net)

1406번: 에디터

---

난이도 : 실버2

풀이 과정 :

일단 시간제한이 0.2초이고 문자열이 십만, 명령어의 개수가 50만이므로

최악의 경우 최대 연산 개수가 십만*50만 = 500억이 된다.

그러면 O(n)으로 짜면 무조건 시간 초과가 나고

선형 시간에 알고리즘을 짜야된다.

선형 시간에 이 문제를 푸는 방법은 바로 연결리스트 자료 구조를 이용하면된다.

배열/벡터와 달리 연결리스트는 특정 인덱스의 원소를 삭제, 추가 하는데 시간복잡도가 O(1)이기 때문에

위 문제를 선형시간에 풀 수있게 된다.

참고로 나는 c++의 stl list를 이용했다 ㅎ

 

코드 :

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

int n;
string s;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    list<char> l;
    cin >> s;
    for (char c : s) l.push_back(c);
    list<char>::iterator t = l.end();
   

    cin >> n;
    while (n--) {
        string cmd;
        cin >> cmd;
        if (cmd == "L") {
            if (t != l.begin()) t--;
        }
        else if (cmd == "D") {
            if (t != l.end()) t++;
        }
        else if (cmd == "B") {
            list<char>::iterator tmp = t;
            if (t != l.begin()) {
                l.erase(--t);
            }
            t = tmp;
        }
        else {
            char c;
            cin >> c;
            l.insert(t, c);
        }
    }

    for (auto it : l) cout << it;

}