백준 1406번 에디터: C언어 풀이

백준 1406번 에디터 문제의 C 언어 풀이입니다.
연결리스트를 사용한 구현 방식을 소개합니다.

전략

연결 리스트를 이용한 구현

스택을 이용한 풀이도 있는 것 같지만 아직 안배웠으니 패스.
정직하게 연결 리스트로 구현했다.

"명령어가 수행되기 전 커서는 문장의 맨 뒤에 위치하고 있다고 한다"
이 조건을 위해 끝에 NUL(\0) 문자를 넣어 두었다.
조건 처리가 훨씬 편리해진다.

코드

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

enum operations
{
    LEFT = 'L',
    RIGHT = 'D',
    DELETE = 'B',
    PREPEND = 'P'
};

struct node
{
    char letter;
    struct node *next;
    struct node *prev;
};

void prepend(struct node *curr, char c);
void delete_prev(struct node *curr);
void print_list(struct node *curr);
void free_list(struct node *tail);

int main(void)
{
    struct node *tail = malloc(sizeof(struct node));
    tail->letter = '\0';
    tail->next = NULL;
    tail->prev = NULL;

    char c;
    while ((c = getchar()) != '\n')
    {
        prepend(tail, c);
    }

    int num_operations;
    scanf("%d\n", &num_operations);

    struct node *curr = tail;

    for (int i = 0; i < num_operations; i++)
    {
        char operation = getchar();
        switch (operation)
        {
            case LEFT:
                curr = (curr->prev != NULL) ? curr->prev : curr;
                break;

            case RIGHT:
                curr = (curr->next != NULL) ? curr->next : curr;
                break;

            case DELETE:
                delete_prev(curr);
                break;

            case PREPEND:
            {
                // Consume space
                getchar();
                char letter = getchar();
                prepend(curr, letter);
                break;
            }
        }
        while (getchar() != '\n');
    }
    print_list(curr);
    free_list(tail);
}

void delete_prev(struct node *curr)
{
    if (curr->prev != NULL)
    {
        struct node *tmp = curr->prev;
        // Linking, if possible
        if (tmp->prev != NULL)
        {
            tmp->prev->next = curr;
        }
        curr->prev = tmp->prev;
        free(tmp);
    }
}

void prepend(struct node *curr, char c)
{
    struct node *new_node = malloc(sizeof(struct node));
    new_node->letter = c;
    new_node->next = curr;
    new_node->prev = curr->prev;

    // Link with existing node if possible
    if (curr->prev != NULL)
    {
        curr->prev->next = new_node;
    }
    curr->prev = new_node;
}

void print_list(struct node *curr)
{
    // Move curr to head
    while (curr->prev != NULL)
    {
        curr = curr->prev;
    }

    while (curr->next != NULL)
    {
        printf("%c", curr->letter);
        curr = curr->next;
    }
    printf("\n");
}

void free_list(struct node *tail)
{
    struct node *curr = tail;
    while (curr != NULL)
    {
        struct node *prev = curr->prev;
        free(curr);
        curr = prev;
    }
}

import sys

it = iter(sys.stdin.read().split())
get_token = lambda: next(it)

left_stack = list(get_token())
right_stack = []

n_operations = int(get_token())

for _ in range(n_operations):
    operations = get_token()
    if operations == 'L':
        if left_stack:
            right_stack.append(left_stack.pop())
    elif operations == 'D':
        if right_stack:
            left_stack.append(right_stack.pop())
    elif operations == 'B':
        if left_stack:
            left_stack.pop()
    else:
        left_stack.append(get_token())

sys.stdout.write(''.join(left_stack + right_stack[::-1]))
sys.stdout.write('\n')