백준 1406 - 에디터(C++/DLL)

문제 https://www.acmicpc.net/problem/1406

1406번: 에디터

 

풀이

DLL을 이용하여 풀 수 있는 문제이다. 

포인트는,

첫 번째로 현재 커서의 위치를 나타내는 cur 포인터가 연산이 끝나고 제자리를 잘 가리키도록 해야 한다는 것이다. 

추가 연산을 한 후에는 새로 생성된 노드를 가리키고, 삭제 연산을 한 후에는 가리키던 노드의 이전 노드를 가리키도록 한다. 왼쪽이나 오른쪽으로 이동하는 연산을 할 때는 연결리스트의 범위를 넘어가지 않도록 한다.

 

두 번째는 연결리스트를 만들 때, head 부분에 노드를 생성하고 시작한다.

커서의 위치가 맨 앞일 경우가 있으므로, 이 경우를 잘 처리하지 않으면 null pointer에 접근할 수도 있다.

head 부분에 내용물이 없는 노드를 생성했으므로, 출력할 때 head의 다음부터 출력하면 된다.

 

코드

#include <iostream>
#include <string>
using namespace std;

typedef struct node
{
    char i;
    struct node*next;
    struct node*prev;
}node;
node*head = 0;
node*cur = 0;

void add(char c)
{
    node*newnode = (node*)malloc(sizeof(node));
    newnode->i=c;
    newnode->next=newnode->prev=0;

    if(head->next==0)
    {
        head->next=newnode;
        newnode->prev=head;
        cur=newnode;
    }
    else if(cur->next==0)
    {
        newnode->prev=cur;
        cur->next=newnode;
        cur=newnode;
    }
    else if(cur->next!=0)
    {
        cur->next->prev=newnode;
        newnode->next=cur->next;
        newnode->prev=cur;
        cur->next=newnode;
        cur=newnode;
    }
}

void Left()
{
    if(cur->prev!=0) cur=cur->prev;
}

void Right()
{
    if(cur->next!=0) cur=cur->next;
}

void delnode()
{
    node*del = cur;
    
    if(del!=head)
    {
        del->prev->next=del->next;
        if(del->next!=0) 
        {
            del->next->prev=del->prev;
            free(del);
        }
        else cur->next=0;
        cur=cur->prev;
    }
}

void printstring()
{
    node*tmp=head->next;
    while(tmp!=0)
    {
        cout<<tmp->i;
        tmp=tmp->next;
    }
}

int main()
{
    head = (node*)malloc(sizeof(node));
    head->next=head->prev=0;
    string s;
    cin>>s;
    int len=s.length();
    for(int i=0; i<len; i++)
    {
        add(s[i]);
    }
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        char c;
        cin>>c;
        if(c=='L') Left();
        else if(c=='D') Right();
        else if(c=='B') delnode();
        else
        {
            char d;
            cin>>d;
            add(d);
        }
    }
    printstring();
}