(C++) - 백준(BOJ) 5397 : 키로거

https://www.acmicpc.net/problem/5397

5397번: 키로거

std::list를 사용해 푼 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

test case t, keyLog, list li를 선언한 뒤 적절히 입력해줍니다. 매 test case마다 li는 clear()해줍니다.

📔 풀이과정

array의 삽입, 삭제 수행시간은 중앙에 값이 삽입 또는 삭제되었을 때 나머지 원소를 당겨주는 시간까지 포함해 O(n)입니다. L이 100만 제한이므로 삭제, 삽입이 많은 경우 O(N^2)까지 가므로 시간초과가 날 수 있습니다. 따라서 삽입 삭제가 O(1)인 double linked list자료구조를 사용해야합니다. 이는 std::list에서 구현된 자료구조로 편하게 내장함수를 사용할 수 있습니다.

 

iterator head를 선언한 뒤 li.begin()으로 초기화해줍니다.

이 후 keyLog의 각 문자를 확인하면서 list를 갱신해줍니다.

1. 현재 문자가 '>'고 head가 li.end()가 아니라면 오른쪽으로 커서를 옮긴다는 의미로 head++해줍니다.

2. 현재 문자가 '<'고 head가 li.begin()이 아니라면 왼쪽으로 커서를 옮긴다는 의미로 head--해줍니다.

3. 현재 문자가 '-'고 head가 li.begin()이 아니라면 커서를 왼쪽으로 한 칸 옮긴 뒤 그 곳의 원소를 삭제해줍니다. 이후 erase 반환값은 삭제되기전 iterator의 오른쪽이기 때문에 그 값을 head에 저장(갱신)해줍니다.

4. 현재 문자가 알파벳이라면 head의 왼쪽에 추가되는 insert함수의 특징을 고려해 해당 문자를 li에 삽입해줍니다.

📔 정답출력

li의 모든 원소를 begin()부터 end()이전까지 출력해줍니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int t;
string keyLog;
list <char> li;
int main(){
    cin >> t;
    while(t--){
        li.clear();
        cin >> keyLog;
        
        auto head = li.begin();

        for(int i = 0; i < keyLog.size(); i++){
            if(keyLog[i] == '>' && head != li.end()) head++;
            if(keyLog[i] == '<' && head != li.begin()) head--;
            if(keyLog[i] == '-' && head != li.begin()) head = li.erase(--head);
            if(keyLog[i] != '>' && keyLog[i] != '<' && keyLog[i] != '-') li.insert(head,keyLog[i]);
        }

        for(auto l : li) cout << l;
        cout << '\n';
    }
}