문제

Example Input/Output

// IN
abcd // 초기 문자열 (영어 소문자, 최대 100,000 글자)
3 // m: 명령어 수 (1 <= m <= 500,000)
B // 커서 왼쪽 삭제 (커서는 처음에 문자열 맨 오른쪽에 위치해 있음)
P d // d 를 커서 왼쪽에 추가
P x // x 를 커서 왼쪽에 추가
L // 커서 왼쪽으로 이동
D // 커서 오른쪽으로 이동
L
P y

// OUT
abcdyx

C++ 풀이

1. 야매 연결리스트

#include <iostream>
#include <algorithm>

using namespace std;

// 바킹독 센세의 야매 연결리스트
const int MAX = 1000005;
char dat[MAX];
int nxt[MAX], pre[MAX];
int unused = 1;

void insert(int addr, char newData)
{
    dat[unused] = newData;
    nxt[unused] = nxt[addr];
    pre[unused] = addr;

    nxt[addr] = unused;
    if (nxt[unused] != -1)
        pre[nxt[unused]] = unused;

    unused++;
}

void erase(int addr)
{
    nxt[pre[addr]] = nxt[addr];
    if (nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
}

void traverse()
{
    int cur = nxt[0];
    while(cur != -1)
    {
        cout << dat[cur];
        cur = nxt[cur];
    }
    cout << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    fill(pre, pre + MAX, -1);
    fill(nxt, nxt + MAX, -1);

    string s;
    cin >> s;

    int cursor = 0;
    for (auto c: s)
    {
        insert(cursor, c);
        cursor = nxt[cursor];
    }

    int m;
    cin >> m;

    for (int i = 0; i < m; i++)
    {
        char command;
        cin >> command;

        if (command == 'L')
        {
            if (pre[cursor] != -1)
                cursor = pre[cursor];
        }
        else if (command == 'D')
        {
            if (nxt[cursor] != -1)
                cursor = nxt[cursor];
        }
        else if (command == 'B')
        {
            if (pre[cursor] == -1)
                continue;
            erase(cursor);
            cursor = pre[cursor];
        }
        else if (command == 'P')
        {
            cin >> command;
            insert(cursor, command);
            cursor = nxt[cursor];
        }
    }
    traverse();
}

2. STL list

#include <iostream>
#include <algorithm>
#include <list>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    list<char> l;

    string s;
    cin >> s;

    for (auto c: s)
        l.push_back(c);

    list<char>::iterator cursor = l.end();
    
    int m;
    cin >> m;

    for (int i = 0; i < m; i++)
    {
        char command;
        cin >> command;

        if (command == 'L')
        {
            if (cursor == l.begin())
                continue;
            cursor--;
        }
        else if (command == 'D')
        {
            if (cursor != l.end())
                cursor++;
        }
        else if (command == 'B')
        {
            if (cursor == l.begin())
                continue;
            cursor = l.erase(--cursor);
        }
        else if (command == 'P')
        {
            cin >> command;
            l.insert(cursor, command);
        }
    }

    for (auto c: l)
        cout << c;
}

메모

• 바킹독 센세의 강의 영상을 한 번 본 이후 풀기 시작

  • 야매 연결리스트는 Dummy Node가 가장 앞에 있고, STL list는 Dummy Node가 가장 뒤에 있다는 댓글을 봤었는데, 그게 힌트가 됐다.
  • 위 그림은 각 풀이 방법 별 커서 위치 (생각하기 쉽게 커서가 데이터 위에 위치하는걸로)

• 야매 연결리스트로 풀 때 버그로 잡는 게 너무 힘들었다.

• STL list로 먼저 푼 다음, 야매 연결리스트를 다시 풀기 시작하니 조금 수월했다.

• 다 풀고 바킹독 센세의 답안과 체크해보니 똑같이 풀어서 안심했다.

• @ TIME: 스택을 이용한 풀이