BOJ)5397 키로거

문제:icpc.me/5397

메모장에 커서의 입력하는 단어와 커서의 움직임과 누른 백스페이스가 기록될 때 최종적으로 남는 단어를 출력하는 문제이다.

중간에 삽입 삭제가 가능한 링크드리스트를 구현하여 해결할 수 있다.

#include <cstdio>
#include <algorithm>
using namespace std;
struct Node {
    char data;
    Node  *prev, *next;
    Node() :data('\0'), prev('\0'), next('\0') {}
    Node(char data, Node* pv, Node* nt) :data(data) {
        prev = pv;
        next = nt;
    }
};
struct list {
    Node *head, *tail, *curr;
    list() {
        head = tail = curr = new Node();
    }
    void add(char x) {
        if (curr == tail) {
            Node* newNode = new Node(x, tail, NULL);
            tail->next = newNode;
            tail = newNode;
            curr = newNode;
        }
        else {
            Node* tNode = curr->next;
            Node* newNode = new Node(x, curr, tNode);
            curr->next = newNode;
            tNode->prev = newNode;
            curr = newNode;
        }
    }
    void sub() {
        if (curr == head) {
            return;
        }
        else if (curr == tail) {
            Node* tNode = tail;
            tail = tail->prev;
            curr = tail;
            delete tNode;
        }
        else {
            Node* tNode = curr;
            curr->prev->next = curr->next;
            curr->next->prev = curr->prev;
            curr = curr->prev;
            delete tNode;
        }
    }
    void moveL() {
        if (curr == head)
            return;
        curr = curr->prev;
    }
    void moveR() {
        if (curr == tail)
            return;
        curr = curr->next;
    }
    void print() {
        Node* tNode = head->next;
        while (tNode != tail) {
            printf("%c", tNode->data);
            tNode = tNode->next;
        }
        printf("%c", tNode->data);
    }
};
int t;
char c[1000001];
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%s", &c);
        list lt;
        for (int i = 0; c[i] != '\0'; i++) {
            if (c[i] == '<')
                lt.moveL();
            else if (c[i] == '>')
                lt.moveR();
            else if (c[i] == '-')
                lt.sub();
            else
                lt.add(c[i]);
        }
        lt.print();
        puts("");
    }
    return 0; 
}