1406번: 에디터

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


$O(l+n)$

linked list 문제

#include<cstdio>
#include<list>
using namespace std;
int n, p, q;
char s[100001];
list<char> l;
int main() {
    scanf("%s", s);
    for (int i = 0; s[i]; i++) l.push_back(s[i]);
    auto it = l.end();
    for (scanf("%d", &n); n--;) {
        scanf(" %c", &p);
        if (p == 'L'&&it != l.begin()) it--;
        if (p == 'D'&&it != l.end()) it++;
        if (p == 'B'&&it != l.begin()) it = l.erase(--it);
        if (p == 'P') scanf(" %c", &q), l.insert(it, q);
    }
    for (auto it : l) putchar(it);
    return 0;
}

5397번: 키로거

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


$O(tl)$

링크드 리스트를 이용한다.

#include<cstdio>
#include<list>
using namespace std;
int t;
char s[1000001];
int main() {
    for (scanf("%d", &t); t--;) {
        list<char> l;
        auto p = l.begin();
        scanf("%s", s);
        for (int i = 0; s[i]; i++) {
            if (s[i] == '-') { if (p != l.begin()) p = l.erase(--p); }
            else if (s[i] == '<') { if (p != l.begin()) p--; }
            else if (s[i] == '>') { if (p != l.end()) p++; }
            else p = l.insert(p, s[i]), p++;
        }
        for (char c : l) putchar(c);
        puts("");
    }
    return 0;
}