[ 백준 / C ] 1406번 : 에디터

1406

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// 노드 구조체 만들기
typedef struct Node
{
    struct Node *pre;
    char data;
    struct Node *next;
} NODE;

NODE *head_p;
NODE *cur_p;
NODE *tail_p;

// 삽입
NODE* insert(char data){
    NODE * newNode = (NODE *)malloc(sizeof(NODE));

    newNode->data = data;

    // 현재 노드가 헤드 노드일 경우
    if(cur_p == head_p){
        cur_p->pre = newNode;
        newNode->next = cur_p;

        newNode->pre = NULL;
        head_p = newNode;
    }
    // 현재 노드가 헤드 노드가 아닐 경우
    else{
        cur_p->pre->next = newNode;
        newNode->pre = cur_p->pre;

        newNode->next = cur_p; 
        cur_p->pre = newNode;   
    }
    return newNode;
}

// 삭제
int delete(){
    // (커서가 문장의 맨 앞이면 무시됨). return 0;
    if(cur_p == head_p){
        return 0;
    }
    
    // 삭제 할 노드 임시 저장
    NODE *delte_node = cur_p->pre;

    // 만약 삭제할 노드의 전 노드가 head 일 경우
    if(cur_p->pre == head_p){
        cur_p->pre = NULL;
        head_p = cur_p;
    }
    // 그 외
    else{
        cur_p->pre->pre->next = cur_p;
        cur_p->pre = cur_p->pre->pre;
    }
            
    // 동적 할당 된 메모리 해제 시켜주기
    free(delte_node);
    return 1; 
}

int main(void){
    // 문자열 입력
    char str[100001] = {0};
    scanf("%s", str);
    int str_len = strlen(str);

    NODE head = {NULL, 0, NULL};
    head_p = &head;
    NODE tail = {head_p, '\0', NULL};
    tail_p = &tail;

    // 현재 노드 마지막 노드로 바꿔주기
    cur_p = tail_p;

    for(int i = 0; i < str_len; i++){
        char data = str[i];
        NODE *newNode = insert(data);
        
        // 만약 첫 문자열이면 head로 바꿔주기
        if(i == 0){
            head_p = newNode;
            head_p->pre = NULL;
        }
    }

    // 명령어 개수 입력
    int command_num = 0;
    scanf("%d", &command_num);
    
    for(int i = 0; i < command_num; i++){
        // 명령어 입력
        char command = 0;
        getchar();
        scanf("%c", &command);

        switch (command)
        {
        // 커서를 왼쪽으로 한 칸 옮김 
        case 'L': 
            if(cur_p == head_p){// (커서가 문장의 맨 앞이면 무시됨)
                break;
            }
            cur_p = cur_p->pre;
            break;
        // 커서를 오른쪽으로 한 칸 옮김 
        case 'D':
            if(cur_p == tail_p){ // (커서가 문장의 맨 뒤이면 무시됨)
                break;
            }
            cur_p = cur_p->next;
            break;
        // 커서 왼쪽에 있는 문자를 삭제함
        case 'B':
            if(delete()){
                str_len --;
            }
            break;
        // 문자를 입력받고, 문자를 커서 왼쪽에 추가함
        case 'P':
            char data = 0;
            getchar();
            scanf("%c", &data);

            insert(data);
            str_len ++;
            
            break;
        }
    }

    // 문자열 출력하고 동적 할당 된 메모리 해제 시켜주기
    cur_p = head_p;
    for(int i = 0; i < str_len; i++){
        head_p = cur_p;
        printf("%c",cur_p->data);
        cur_p = cur_p->next;

        free(head_p);
    }
    return 0;
}

---

하 진짜 오래걸렸다...

 

11월 27일날에 처음 만든 코드는 찾아서 삭제할 때에도 O(n), 삽입도 O(n) 으로 시간 초과가 났다.

그래서 질문 게시판에서 찾아보니 삽입과 삭제가 O(1)인 이중연결리스트를 사용하여서 풀어야한다고 했다...

근데 그 시간이 너무 늦어서 다음에 풀자 하고 넘겼다.

처음 만든 코드

#include <stdio.h>
#include <string.h>

int main(void){
    char str[600000] = {0};
    scanf("%s", &str);

    int test_case = 0;
    scanf("%d", &test_case);
    getchar();

    
    int len = strlen(str);
    int cursor = len;
    for(int i = 0; i < test_case; i++){
        char command = 0;
        scanf("%c", &command);
        getchar();

        switch (command)
        {
        case 'L':
            if(cursor == 0){
                break;
            }
            else{
                cursor --;
            }
            break;
        case 'D':
            if(cursor == len){
                break;
            }
            else{
                cursor ++;
            }
            break;
        case 'B':
            if(cursor == 0){
                break;
            }
            else{
                for(int j = cursor-1; j < len; j++){
                    str[j] = str[j+1];
                }
                cursor--;
                len--;
            }
            break;
            
        case 'P':
            char word = 0;
            scanf("%c", &word);
            getchar();

            for(int j = len; j > (cursor-1); j--){
                str[j] = str[j-1];
            }
            str[cursor++] = word;
            str[++len] = '\0';
            break;
        }
    }

    printf("%s", str);
    return 0;
}

 

 

그리고 오늘은 좀 여유가 나서 다시 풀어보았다...

한 문제를 맞추는데는 5시간 걸렸던 것 같다. ㅋㅋ

옛날에 이중 링크드리스트 자바로 구현한적있어서 흐름 자체는 이해를 하고 있었지만,,,,

코드를 만드는데 너무 오래걸렸다..ㅎㅎ..ㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜ

 

근데 처음 만든 코드가 너무 너무너문어뭠너ㅜ머ㅜ머ㅜㄴ머ㅜㄴ머ㅜ너ㅜㅁ너눠 마음에 안드는것..

처음 문자열 입력 할 때 삽입하는 것이랑 추가 문자열 삽입할때가 따로 있는거...

어짜피 똑같이 삽입하는건데,,, 

 

그래서 다시 구조를 바꾸기 시작함요..

함수로 만들고

따로있는 삽입들 하나로 합쳐주는 작업을 했으요!! << 이것도 오래걸림..ㅋ..

 

그래서 최종 코드가 맨 위의 코드에유

사실 위에 코드도 좋은 코드라고 생각이 들진 않는다.

더 나은 코드가 있을 것 같은데 지금 코드도 나름 열심히 한 결과물이라 만족하기로 했당...

처음 맞춘 코드

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct Node
{
    struct Node *pre;
    char data;
    struct Node *next;
} NODE;

int main(void){
    NODE head = {NULL, 0, NULL};
    NODE tail = {NULL, 0, NULL};
    NODE *head_p = &head;
    NODE *cur_p = head_p;
    NODE *tail_p = &tail;

    char str[100001] = {0};
    scanf("%s", str);

    int str_len = strlen(str);
    int node_count = 0;
    for(int i = 0; i <= str_len; i++){
        char data = str[i];

        NODE *newNode = (NODE *)malloc(sizeof(NODE));
        newNode->data = data;
        
        if(i==0){
            head_p = newNode;
        }
        else{
            newNode->pre = cur_p;
            cur_p->next = newNode;
        }

        if(data == '\0'){
            tail_p = newNode;
            tail_p->next = NULL;
        }

        cur_p = newNode;
        node_count++;
    }

    int test_case = 0;
    scanf("%d", &test_case);
    
    int cursor = node_count-1;
    for(int i = 0; i < test_case; i++){
        char command = 0;
        getchar();
        scanf("%c", &command);

        switch (command)
        {
        case 'L':
            if(cur_p == head_p){
                break;
            }
            cur_p = cur_p->pre;
            break;
        case 'D':
            if(cur_p == tail_p){
                break;
            }
            cur_p = cur_p->next;
            break;
        case 'B':
            if(cur_p == head_p){
                break;
            }
            
            NODE *delte_node = cur_p->pre;

            if(cur_p->pre == head_p){
                cur_p->pre = NULL;
                head_p = cur_p;
            }
            else{
                cur_p->pre->pre->next = cur_p;
                cur_p->pre = cur_p->pre->pre;
            }
            
            free(delte_node); 
            node_count --;

            break;
        case 'P':
            NODE * newNode = (NODE *)malloc(sizeof(NODE));
            node_count ++;
            getchar();
            scanf("%c", &(newNode->data));

            if(cur_p == head_p){
                cur_p->pre = newNode;
                newNode->next = cur_p;

                newNode->pre = NULL;
                head_p = newNode;
            }
            else{
                cur_p->pre->next = newNode;
                newNode->pre = cur_p->pre;

                newNode->next = cur_p; 
                cur_p->pre = newNode;   
            }

            
            break;
        }
    }

    cur_p = head_p;
    for(int i = 0; i < node_count; i++){
        head_p = cur_p;
        if(cur_p != tail_p){
            printf("%c",cur_p->data);
            cur_p = cur_p->next;
        }

        free(head_p);
    }
    return 0;
}