[백준 5397] 키로거 - C++로 구현한 연결리스트

문제 개요

• 문제 번호: 5397
• 제목: 키로거
• 난이도: 실버 2
• 링크: 백준 5397번

---

문제 설명

창영이라는 나쁜 친구가 강산이의 번호를 훔치기위해 키로거를 강산이 컴퓨터에 설치했다. 이 키로거는 강산이가 입력하는 입력 문자와 방향키(<, >), 백스페이스(-)를 추적한다. 한줄에 입력되는 입력을 통해 강산이의 비밀번호를 알아내는 문제다.

---

접근 방법

문자열을 입력받아 문자열을 순회하면서 다음과 로직을 만든다

1. '<' 인 경우: 커서를 왼쪽으로 미룬다. -> cursor--

2. '>'인 경우: 커서를 오른쪽으로 미룬다. -> cursor++

3. '-'인 경우: 커서 기준으로 왼쪽 문자를 지운다.

4. 문자인 경우: 커서 기준으로 오른쪽에 문자를 삽입하고 커서를 오른쪽으로 미룬다.

문제 조건에서 문자열 길이가 최대 1,000,000일 수 있다 이때 문자를 계속 맨 앞에 삽입하게 될때를 고려해야한다. 단순 배열로 만들게 되면 시간 복잡도가 엄청날거니 여기에는 연결리스트를 사용하는게 적합하다.

여기서 주의할점이 커서를 움직일때 가장 끝부분에 있을때는 한번씩 체크를 해야한다.

if(c == '<'){
    if(cursor != L.begin()) cursor--;
}
else if(c == '>'){
    if(cursor != L.end()) cursor++;
}
else if(c == '-'){
    if(cursor != L.begin()) cursor = L.erase(--cursor);
}

 

---

구현 코드

#include<iostream>
#include<list>
#define endl "\n"

using namespace std;

int t;
int main(){
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> t;

    while (t--)
    {
        string line;
        list<char> L;
        list<char>::iterator cursor = L.begin();

        cin >> line;
        for(auto c : line){
            if(c == '<'){
                if(cursor != L.begin()) cursor--;
            }
            else if(c == '>'){
                if(cursor != L.end()) cursor++;
            }
            else if(c == '-'){
                if(cursor != L.begin()) cursor = L.erase(--cursor);
            }
            else{
                L.insert(cursor, c);
            }
        }

        for(auto c : L) cout << c;
        cout << endl;
    }
    
}

---

시간 복잡도

• O(t*n): t는 테스트 갯수 n은 문자열 L의 길이

---