[연결리스트]백준 5397번 키로거

백준5397번

연결리스트를 사용하는 문제의 대표적인 유형 중 하나는 텍스트 편집기 혹은 텍스트 입력기를 구현하는 문제이다.

커서를 이동하는 경우

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

   연결리스트의 iterator가 begin 이 아닌 경우에는 iterator를 1 감소한다.

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

   연결리스트의 iterator가 end가 아닌 경우에 iterator를 1 증가시킨다.

문자를 삭제하는 경우

커서가 iterator를 기준으로 왼쪽에 위치하는지 오른쪽에 위치하는지 명확하게 머리속에 그려놓고 시작해야 한다.

나는 커서가 Iterator가 가리키는 문자 기준으로 왼쪽에 있다고 가정하고 코드를 작성하였다.

가령 ABCD가 있고 iterator가 D를 가리키고 있다면 커서는 ABC^D 인 경우를 생각했다. (^가 커서의 위치)

따라서 삭제 연산을 하는 경우는 iterator가 begin이 아니어야 하고, erase 함수는 자신이 가리키고 있는 인덱스를 삭제하기 때문에 iterator를 1 감소시키고 erase를 수행하였다. 또한 erase 함수는 자신이 삭제한 원소의 다음 원소를 가리키는 iterator를 반환한다는 사실을 기억해야 한다.

문자를 삽입하는 경우

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

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

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

for(auto x:List){

}

다음과 같은 방법으로 연결리스트를 순회할 수 있다. 다만 주의할 점은, 순회하는 for문 내에서 연결 리스트의 원소가 추가 혹은 삭제되는 경우 런타임 에러가 발생할 수 있다.

#include <iostream>
#include <list>
#include <string>
using namespace std;

int main(){
    int cases;
    cin >> cases;
    
    while(cases--){
        string password;
        list<char> l;
        //l.push_back('-');
        cin >> password;
        list<char>::iterator pos = l.end();
        for(int i=0;i<password.size();i++){
            if(password[i] == '<'){
                if(pos != l.begin()) pos--;
            }
            else if(password[i] == '>'){
                if(pos != l.end()) pos++;
            }
            else if(password[i] == '-'){
                if(pos != l.begin()){
                    pos--;
                    pos = l.erase(pos);
                }
            }
            else{
                
                 l.insert(pos, password[i]);
            }
            //if(pos == l.end()) pos--;
        }
        for(auto x:l){
            if(x != '-')cout << x;
        }
        cout << "\n";
    }
   
}