[Jungol] 정올 3123 키로거(Keylogger)

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2405&sca=50&page=21

Approach

이중 연결 리스트를 만들어 cur 포인터를 관리합니다.　

① '<'인 경우 이동 가능 cur를 왼쪽으로 이동

② '>'인 경우 이동 가능 cur를 오른쪽으로 이동

③ '-'인 경우 지울 수 있다면 cur의 데이터를 지우고 cur를 왼쪽 노드로 이동

④ 그 외(입력)의 경우 cur의 next에 새로운 노드를 추가하고 cur가 새로운 노드를 참조하도록 한다.

 

※ 라이브러리를 이용한 풀이: [BOJ] 5397 키로거 

[BOJ] 백준 5397 키로거

 

---

#include <stdio.h>
const int LM = (int)1e6 + 10;
struct Node {
       char data;
       Node *prev, * next;
       Node* alloc(char nd, Node* cur) {
              data = nd, prev = cur, next = cur->next;
              cur->next = this;
              if (next) next->prev = this;
              return this;
       }
       Node* erase() {
              prev->next = next;
              if (next) next->prev = prev;
              return prev;
       }
}buf[LM], *head, *cur;
int bcnt;
void backSpace() {
       // cur가 제일 왼쪽에 위치한 경우
       if (cur == head) return;
       cur = cur->erase();
}
void leftShift() {
       // cur가 제일 왼쪽에 위치한 경우
       if (cur == head) return;
       cur = cur->prev;
}
void rightShift() {
       // cur가 제일 오른쪽에 위치한 경우
       if (cur->next == NULL) return;
       cur = cur->next;
}
void insert(char ch) {
       cur = buf[bcnt++].alloc(ch, cur);
}
void output() {
       // head 자체는 더미노드이므로 head->next
       Node* p = head->next;
       for (; p; p = p->next) {
              printf("%c", p->data);
       }
       puts("");
}
char str[LM];
int main() {
       int tc;
       scanf("%d", &tc);
       while (tc--) {
              scanf("%s", str);
              bcnt = 1;
              head = cur = buf; // &buf[0]
              cur->prev = cur->next = NULL;
              for (int i = 0; str[i]; ++i) {
                     if (str[i] == '-') backSpace();
                     else if (str[i] == '<') leftShift();
                     else if (str[i] == '>') rightShift();
                     else insert(str[i]);
              }
              output();
       }
       return 0;
}