[BOJ] #5397 키로거

시간 제한	메모리 제한	정답 비율
1 초	256MB	23.480 %

 

5397번: 키로거

스택 구현해서 풀긔-⭐

문제

해결

key point, 커서의 이동을 구현한다. → cur

head → 스택 ← tail

• 스택을 head와 tail이 가리키는 구조로 만들고
• 커서 역할을 하는 포인터 cur을 이용하여
• < 을 입력받으면 cur를 왼쪽으로,
• > 을 입력받으면 cur를 오른쪽으로 이동하고
• - 을 입력받으면 커서를 기준으로 이전 노드와 이후노드를 서로 연결시켜주고,
                                              커서가 가르키고 있던 노드를 삭제한다.
• 그 외의 문자를 입력받으면 새로운 노드를 생성해서 스택과 연결해준다.

코드

메모리	시간
72656KB	240 ms

#include<iostream>
 
// 더블 링크드 리스트
// 처음과 끝을 준 것. 
class Node {
public:
    char data;
    Node* prev;
    Node* next;
    Node() {
        prev = 0;
        next = 0;
    }
};
 
Node head;
Node tail;
char str[1000001];
 
 
int main() {
    int T;
    scanf("%d", &T);
    // 문자열을 저장할 때 범위는  아스키코드. 
    //포인터가 이 값에 도달했을 때 끝임을 알게하기 위해서 
    head.data = -1;
    tail.data = -1;
 
    while(T--) {
        head.next = &tail;
        tail.prev = &head;
 
        scanf("%s", str);
        Node* cur; // 입력과 커서의 이동 수행.
        cur = &head;
 
        for (int i = 0; str[i]; ++i) {
            if (str[i] == '<') {
                if (cur != &head) cur = cur->prev;
            }
            else if (str[i] == '>') {
                // 헤드에서 tail 직전까지만 움직일수 있는 노드.
                if (cur->next != &tail) cur = cur->next;
            }
            else if (str[i] == '-') {
                // 메모장의 커서를 봤을 때 오른쪽에 새로운 입력이 들어온다고 생각하고
                // 백스페이스를 입력받으면 커서 앞의 문자 하나 삭제. 
                if (cur != &head) {
                    Node* tmp = cur;
                    cur->prev->next = cur->next;
                    cur->next->prev = cur->prev;
                    cur = cur->prev;
                    free(tmp);
                }
            }
            else {
                Node* nNode = new Node;
                nNode->data = str[i];
                nNode->prev = cur;
                nNode->next = cur->next;
                //nNode->next->prev = nNode;
                cur->next->prev = nNode;
                cur->next = nNode;
                cur = nNode;
            }
        }
        Node* t = head.next;
        while (t->data != -1) {
            printf("%c", t->data);
            t = t->next;
        }
        printf("\n");
    }
 
    return 0;
}