티스토리 뷰

알고리즘 관련/BOJ

BOJ)5397 키로거

JASON 자손9319 2017. 3. 28. 13:31

문제:icpc.me/5397


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#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
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)5427 불  (0) 2017.03.30
BOJ)1745 숨기  (0) 2017.03.29
BOJ)5397 키로거  (0) 2017.03.28
BOJ)2075 N번째 큰 수  (0) 2017.03.27
BOJ)1326 폴짝폴짝  (0) 2017.03.26
BOJ)13166 범죄 파티  (0) 2017.03.25
댓글
댓글쓰기 폼