[백준 1406] 알고리즘 107일차 : 에디터

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

1406번: 에디터

연결리스트 C++ 

커서를 좌우로 옮기거나 커서 앞쪽 문자를 지우거나 커서 왼쪽에 문자를 추가하는 명령들을 수행한 후

최종 문자열을 출력하는 문제이다.

 

접근방법

이중연결리스트를 만들어서 풀었다.

 

오답노트

1. 문자열 받을때 배열크기 100001로 설정 '\0' 간과함

2. 출력할때 마지막에 "\n"해줘야함. 결과값이 늘 하나라 안해도 되는줄 알았는데 46분동안 헤매던게 결국 이거였음. 진짜 킹받음.

 

소스코드

#include <iostream>
using namespace std;

struct Node{
    char data;
    Node* next;
    Node* prev;
};

Node node[600002];
int nodeCnt;
Node* head;
Node* tail;
Node* cursor;


Node* getNode(char data){
    node[nodeCnt].data = data;
    node[nodeCnt].prev = nullptr;
    node[nodeCnt].next = nullptr;
    return &node[nodeCnt++];
}

void init(){
    nodeCnt = 0;
    head = getNode(0);
    tail = getNode(0);
    head->next = tail;
    tail->prev = head;
    cursor = tail;
}

void insert(char data){
    Node* n = getNode(data);
    n->prev = cursor->prev;
    cursor->prev->next = n;
    n->next = cursor;
    cursor->prev = n;
}

void initStr(char* str){
    int i = 0;
    while(str[i] != '\0'){
        insert(str[i++]);
    }
}

void deleteNode(){
    //cursor의 prev를 지움
    if(cursor->prev != head){
        cursor->prev->prev->next = cursor;
        cursor->prev = cursor->prev->prev;
    }
}

void left(){
    if(cursor->prev != head){
        cursor = cursor->prev;
    }
}

void right(){
    if(cursor != tail){
        cursor = cursor->next;
    }
}

int main(){
    //input
    char str[100001];
    cin >> str;
    
    //process & input
    init();
    initStr(str);
    
    int n;
    cin >> n;
    for(int i = 0 ; i < n ; i++){
        char ch;
        cin >> ch;
        switch (ch) {
            case 'L':
                left();
                break;
            case 'D':
                right();
                break;
            case 'B':
                deleteNode();
                break;
            case 'P':
                char m;
                cin >> m;
                insert(m);
                break;
            default:
                break;
        }
    }
    
    //output
    cursor = head;
    while(cursor->next != tail){
        cout << cursor->next->data;
        cursor = cursor->next;
    }
    cout << "\n";
    return 0;
}