[연결리스트]백준1406번 에디터

백준1406번

연결리스트의 대표 유형 중 하나는 텍스트 에디터를 구현하는 것이다.

우리가 연결리스트에서 특정 위치를 가리킬 때는 iterator를 사용해 원소를 기리키지만, 텍스트 에디터에서 커서는 문자와 문자 사이에 있다. 따라서 커서가 현재 iterator가 가리키는 원소의 왼쪽에 있는지 오른쪽에 있는지 명확하게 결정하고 구현해야 한다. 나는 커서가 iterator가 가리키는 원소의 왼쪽에 있다고 가정하고 구현하였다.

추가로, 연결리스트에서 begin은 첫 번째 원소가 있는 위치를 가리키지만 end는 마지막 원소 다음에 연결리스트의 끝을 가리키는 iterator를 반환한다는 사실을 잘 알고있어야 한다.

커서를 이동하는 경우

1. 커서를 왼쪽으로 이동하는 경우

   iterator가 연결 리스트의 첫 번째 원소를 가리키고 있는 것이 아니라면 iterator를 1 감소시킨다.

2. 커서를 오른쪽으로 이동하는 경우

   iterator가 연결 리스트의 마지막을 나타내는 iterator가 아니라면 iterator를 1 증가시킨다.

문자를 삭제하는 경우

커서가 iterator가 가리키는 원소의 왼쪽에 있다고 가리키기 때문에, 현재 iterator가 가리키는 원소의 이전 원소를 삭제해야 한다. 따라서 iterator의 원소를 1 감소시키고 erase 함수를 사용해 삭제를 수행해야 한다. 다만 이 때, iterator는 연결리스트의 begin이 아니어야 한다.

문자를 삽입하는 경우

커서가 iterator 기준으로 왼쪽에 있고, 문자를 삽입하는 경우는 커서가 있는 위치에 문자를 삽입해야 하기 때문에 그대로 수행해주면 된다.

연결리스트를 출력하는 경우 (순회)

auto를 이용한 for문을 사용하면 손쉽게 연결리스트를 순회할 수 있다.

for(auto x: List){

}

이 때 주의할 점은, 순회하는 for문 내에서 연결 리스트의 원소가 추가 혹은 삭제되는 경우 런타임 에러가 발생할 수 있다.

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

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    string s;
    cin >> s;

    list<char> L;
    list<char>::iterator cursor; 
    for(int i=0;i<s.size();i++){
       L.push_back(s[i]); 
    }
    // L.push_back('F');
    cursor = L.end(); // pointing F
    // cursor--;
    int num;
    cin >> num;

    for(int i=0;i<num;i++){
        char tmp;
        cin >> tmp;
        if(tmp == 'L'){
           if(cursor != L.begin()) cursor --;
        }
        else if(tmp == 'D'){
            if(cursor != L.end()) cursor ++;
        } 
        else if(tmp == 'B'){
            if(cursor != L.begin()){

                    // cout << "erase else!!\n";
                        cursor--;
                        cursor = L.erase(cursor);
            }
        }
        else if(tmp == 'P'){
            char tmp2;
            cin >> tmp2;
            L.insert(cursor,tmp2);

        }
        // for(auto j:L) cout << j;
        //     cout << "\n" << *cursor << "\n";
    }

    for(auto j:L) cout << j;

}