[C++] 백준 1406번: 에디터 - Linked List

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

1406번: 에디터

 

Linked List를 배우고

바로 실전에 적용하기로 마음먹었다

 

그래서 도전한 백준 1406번 에디터 문제..

(알고리즘 분류 -> 연결 리스트 검색)

 

알고리즘 분류는 연결리스트와 스택이었는데,

스택은 거들떠도 안보고 무조건 연결리스트만 고집했다.

 

처음에는 순조롭게 코드를 짜다가

어느 순간부터 이상한걸 느꼈는데,

내가 아는 연결리스트는 단방향인데

이것은 L 과 D로 좌우를 오고가며 단순 연결 리스트가 아니라 이중 연결 리스트임을 알게 되었다.

 

이제 막 링크드리스트를 처음 배운 초짜에게 넘 가혹한 것도 싶었지만

그래도 구글링 없이 대가리만 굴려서 열심히 짰던 코드이다.

 

글을 쓰는 기준 어제 13시부터 18시까지 거의 5시간을 고민하다 3번의 WA를 받았는데,

너무 빡쳐서 오늘 일어나 부대 복귀하기 전에 다시 잡았다.

 

결과는 AC..

처음에 cursor위치가 해당 데이터 앞을 의미하는지, 혹은 뒤를 의미하는지 계속 헷갈려서 WA를 받았고,

오늘 아침에 cursor 위치는 해당 데이터 오른쪽으로 정하자 하고 처음부터 다시 짰다.

 

#include <iostream>
using namespace std;
struct node {
    char data;
    node* prev;
    node* next;
};
class List {
public:
    void AddNode(char c) {
        node* temp = new node;
        temp->data = c;
        if (head == nullptr) {
            head = temp;
            tail = temp;
            cursor = tail;
            cursor->next = nullptr;
        }
        else {
            if (cursor == nullptr) {
                temp->next = head;
                head->prev = temp;
                head = temp;
                cursor = head;
            }
            else if (cursor == tail) {
                tail->next = temp;
                temp->prev = tail;
                tail = temp;
                cursor = tail;
                cursor->next = nullptr;
            }
            else {
                temp->prev = cursor;
                temp->next = cursor->next;
                cursor->next = temp;
                temp->next->prev = temp;
                cursor = temp;
            }
        }
    }
    void Cursor_L() {
        if (cursor != head && cursor!=nullptr) {
            cursor = cursor->prev;
        }
        else {
            cursor = nullptr;
        }
    }
    void Cursor_D() {
        if (cursor == nullptr) {
            if (head != nullptr) {
                cursor = head;
            }
        }
        else if (cursor != tail) {
            cursor = cursor->next;
        }
    }
    void DeleteNode() {
        if (cursor == head) {
            if (cursor != nullptr) {
                if (cursor->next == nullptr) {
                    head = nullptr;
                }
                else {
                    head = cursor->next;
                }
                cursor = nullptr;
            }
        }
        else if (cursor == tail) {
            tail = cursor->prev;
            tail->next = nullptr;
            cursor = tail;
            cursor->next = nullptr;
        }
        else if(cursor!=nullptr) {
            node* temp = cursor->prev;
            temp->next = cursor->next;
            temp->next->prev = cursor->prev;
            cursor = temp;
        }
    }
    void Print() {
        while (head!=nullptr) {
            cout << head->data;
            head = head->next;
        }
    }
private:
    node* head = nullptr;
    node* tail = nullptr;
    node* cursor = nullptr;
};
int main() {
    string s;
    List list;
    int n;
    char x, y;
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        list.AddNode(s[i]);
    }
    cin >> n;
    while (n--) {
        cin >> x;
        if (x == 'P') {
            cin >> y;
            list.AddNode(y);
        }
        else {
            if (x == 'L') {
                list.Cursor_L();
            }
            else if (x == 'D') {
                list.Cursor_D();
            }
            else {
                list.DeleteNode();
            }
        }
    }
    list.Print();
}