5397)키로거

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

문제를 이해하기 위해 메모장을 열어서 확인해보자.

키로거가 ab<<bcd를 기록했다고 해보자

ab를 입력하고 커서가 앞쪽으로 두 번 이동한다.

그리고 bcd가 입력되므로 bcdab를 입력한 것이다.

삽입과 삭제가 쉬워야 하니 이중 연결 리스트를 사용하는 것이 좋을 것같다.

<를 읽으면 이중 연결리스트의 어떤 노드를 가리켰던 커서가 왼쪽 노드를 가리키게 하고

>를 읽으면 커서가 가리키는 노드에서 오른쪽 노드를 가리키게 한다. 

-를 읽으면 커서가 가리키는 노드를 삭제한다.

이중 연결 리스트의 연산의 삽입과 삭제 연산을 구현해야 한다.

계속 틀려서 테스트 케이스를 뜯어보고 예외 처리를 한지라 코드가 굉장히 지저분하다.

(이 문제의 해답은 스택을 사용함)

#include<stdio.h>
#define LENGTH 1000010
 
struct DOUBLE_LINK{
    struct DOUBLE_LINK *left;
    char data;
    struct DOUBLE_LINK *right;
};
 
struct DOUBLE_LINK *password = NULL;
struct DOUBLE_LINK *t = NULL;
 
void createNode(char c) {
    struct DOUBLE_LINK *oldNode;
    oldNode = (struct DOUBLE_LINK *)malloc(sizeof(struct DOUBLE_LINK));
    
    oldNode->left = NULL;
    oldNode->data = c;
    oldNode->right = NULL;
    
    if (t == NULL && password == NULL) {
        password = oldNode;
        t = password;
    }
    else if(t == NULL && password != NULL){
            oldNode->right = password;
            password->left = oldNode;
 
            password = oldNode;
            t = password;
    }
    else if (t->right != NULL) {
        oldNode->right = t->right;
        t->right->left = oldNode;
 
        oldNode->left = t;
        t->right = oldNode;
        t = t->right;
    }
    else if (t->right == NULL) {
        oldNode->left = t;
        t->right = oldNode;
        t = t->right;
    }
}
 
void showData() {
    struct DOUBLE_LINK *p = password;
 
    while (p != NULL) {
        printf("%c",p->data);
        p = p->right;
    }
    printf("\n");
}
 
void deleteAllNode(){
    struct DOUBLE_LINK *p = password;
    struct DOUBLE_LINK *q;
 
    while (p != NULL) {
        q = p;
        p = p->right;
        free(q);
    }
 
    password = NULL;
    t = password;
}
 
void deleteNode() {
    if (t != NULL) {
        struct DOUBLE_LINK *oldNode;
        oldNode = t;
 
        if (t->right == NULL) {
            if (password != t) {
                t->left->right = NULL;
                t = t->left;
            }
            else {
                password = NULL;
                t = password;
            }
        }
        else if (t->left == NULL) {
            password = password->right;
            password->left = NULL;
            t = t->left;
        }
        else {
            t->left->right = t->right;
            t->right->left = t->left;
            t = t->left;
        }
 
        free(oldNode);
    }
}
 
void excute(char c) {
    switch (c)
    {
    case '<':
        if (t != NULL) {
            t = t->left;
        }
        break;
    case '>':
        if (t != NULL) {
            if(t->right != NULL) t = t->right;
        }
        else {
            if (password != NULL) t = password;
        }
        break;
    case '-':
        deleteNode();
        break;
    }
}
 
int main() {
    int N;
    char L[LENGTH];
 
    scanf("%d",&N);
    for (int i = 0; i < N;i++) {
        scanf("%s",L);
        for (int j = 0; L[j] != NULL;j++) {
            if (L[j]!='<'&&L[j] != '>'&&L[j] != '-') {
                createNode(L[j]);
            }
            else {
                excute(L[j]);
            }
        }
        showData();
        deleteAllNode();
    }
 
    system("pause");
    return 0;
}