[백준 5397번] 키로거

---

문제 화면

문제 링크 : https://www.acmicpc.net/problem/5397

문제 풀이

이 문제는 stack이나 linked list를 사용해 키로거를 구현하는 문제이다(1406번 에디터문제와 거의 동일하다).

stack이나 linked list를 사용할 줄 아는지 물어보는 수준의 문제이기 때문에 stack이나 linked list의 자료구조를 알고 stl stack나 linked list의 문법을 사용할 줄 안다면 어렵지 않은 문제이다. stl 컨테이너들 사용법이 가물가물해서 다시 익힐겸 풀어봤다.

stack의 경우 현재 커서를 기준으로 왼쪽의 문자들과 오른쪽의 문자들을 별도의 stack에 보관하는 방식으로 구현하고 linked list의 경우 insert() 와 erase() 함수를 제공해주기 때문에 하나의 list로 풀 수 있었다.

linked list에서 몇가지 유의할 점은 다음과 같다.

1. insert() 와 erase() 함수를 쓸 때 단순 index가 아닌 iterator로 접근해야한다.
2. insert()와 달리 erase()를 사용할 경우 iterator를 반환받아서 갱신시켜주어야 한다.
3. insert()의 경우 iterator 왼편에 새로운 수 삽입, iterator는 원래 가리키던 수를 가리키고 erase()의 경우 iterator가 가리키던 수 지워버리고, 우측에 있는 수를 가리키게 된다.

제출 코드(stack 사용)

#include <iostream>
#include <stack>

using namespace std;

stack<char> l;
stack<char> r;


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

    int a;
    string s;
    cin >> a;
    for(int i = 0 ; i < a ; i++) {
        cin >> s;
        for(int j = 0 ; j < s.length() ; j++) {
            if(s[j]=='<') {
                if(!l.empty()) {
                    r.push(l.top());
                    l.pop();
                }
            }

            else if(s[j]=='>') {
                if(!r.empty()) {
                    l.push(r.top());
                    r.pop();
                }
            }

            else if(s[j]=='-') {
                if(!l.empty()){
                    l.pop();
                }
            }

            else {
                l.push(s[j]);
            }
        }

        while(!l.empty()) {
            r.push(l.top());
            l.pop();
        }

        while(!r.empty()) {
            cout << r.top();
            r.pop();
        }
        cout << "\n";

    }
    
    return 0;
}

제출 코드(linked list사용)

#include <iostream>
#include <list>

using namespace std;

int main(void) {
    int a;
    string s;
    
    cin >> a;
    for(int i = 0 ; i < a ; i++) {
        cin >> s;
        list<char> l;
        //list<char>::iterator index = l.end(); / 이렇게 써도 되고
        auto index = l.end();                   // auto로 자동 형변환 해도 된다
                
        for(int j = 0 ; j < s.length() ; j++) {
            if(s[j]=='<') {
                if(index!=l.begin()) index--;
            }
            else if(s[j]=='>') {
                 if(index!=l.end()) index++;
            }
            else if(s[j]=='-') {
                if(index!=l.begin()) {
                    index--;
                    index = l.erase(index);
                }
            }
            else {
                l.insert(index, s[j]);
            }
        }

        for(auto i = l.begin() ; i!=l.end() ; i++) {
            cout << *i;
        }

        cout << "\n";
        //l.clear(); // for 문 돌 때마다 연결리스트를 재선언 해주기 때문에 없어도 된다
    }
    return 0;
}

결론

이 문제는 stack이나 linked list의 성질을 이용해 문제를 풀 수 있는지를 물어보는 기본적인 문제라고 생각한다. 알고리즘 문제를 풀 때 stack이나 linked list를 잘 아는 것은 중요하기 때문에 자료구조를 잘 이용할 수 있도록 기초를 다지기에 좋은 문제라고 생각한다.