190224 BOJ 1406번 에디터

이중 연결 리스트

- 이중 연결 리스트를 처음으로 직접 구현해서 풀었다.

- 삼성 B형을 대비해서 구현 연습을 계속 해야겠다.

- 끝에 널문자를 출력해서 계속 오답이였다.....

풀이

1. 커서를 좌, 우로 이동하므로 이중 연결 리스트를 구현한다.

2. head와 tail에 유의하여 문제 조건에 맞게 함수를 구현한다.

3. 널문자를 출력하지 않도록 조심한다.

소스 코드

#include <iostream>
#include <string>
#define sws ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;
struct node{
    char data;
    node *next, *prev;
};
node *head = (node*)malloc(sizeof(node));
node *tail = (node*)malloc(sizeof(node));
void init() {
    head->data = NULL;
    head->prev = NULL;
    head->next = tail;
    tail->data = NULL;
    tail->prev = head;
    tail->next = NULL;
}
void add(node *cur, char data) {
    node *newNode = (node*)malloc(sizeof(node));
    cur->prev->next = newNode;
    newNode->data = data;
    newNode->next = cur;
    newNode->prev = cur->prev;
    cur->prev = newNode;
}
void del(node *cur) {
    cur->prev->prev->next = cur;
    node *tmp = cur->prev;
    cur->prev = cur->prev->prev;
    free(tmp);
}
int main() {
    sws;
    init();
    int N;
    char cmd, x;
    string s;
    cin >> s;
    for (char c : s) add(tail, c);
    cin >> N;
    node *cur = tail;
    while (N--) {
        cin >> cmd;
        switch (cmd)
        {
        case 'L':
            if(cur != head->next) cur = cur->prev;
            break;
        case 'D':
            if (cur != tail) cur = cur->next;
            break;
        case 'B':
            if (cur != head->next) del(cur);
            break;
        case 'P':
            cin >> x;
            add(cur, x);
            break;
        default:
            break;
        }
    }
    cur = head->next;
    while (cur != tail) {
        cout << cur->data;
        cur = cur->next;
    }
}