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

[ 문제링크 ]

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

 

🚩 조건

1. 키로거는 사용자가 키보드를 누른 명령을 모두 기록함
2. 백스페이스 : "-" / 커서의 바로 앞에 글자가 존재한다면, 그 글자를 지움
   화살표 : "<", ">" / 커서의 위치를 움직일 수 있다면, 왼쪽 또는 오른쪽으로 1만큼 움직임
   나머지 문자는 비밀번호의 일부
3. 각 테스트 케이스에 대해 비밀번호를 출력해라

 

 

🚩 접근

화살표를 통해 커서를 이동하고 그 지점에서 삽입/삭제가 이뤄져야 함 -> 연결 리스트로 구현하자.

연결리스트는 구조체로 구현하거나, STL list로 구현할 수 있다.

1) 구조체

2) STL list ([참고] 티스토리)

- 삽입

• push_front(element) : 리스트 맨 앞에 원소 추가
• push_back(element) : 리스트 맨 뒤에 원소 추가
• insert(iterator, element) : iterator가 가리키는 부분의 앞에 원소 추가

 

- 삭제

• pop_front() : 리스트 맨 앞에 원소 삭제
• pop_back() : 리스트 맨 뒤에 원소 삭제
• erase(iterator) : iterator가 가리키는 부분의 원소 삭제

 

- 조회

• front() : 첫번째 원소 반환
• back() : 마지막 원소 반환
• *iterator : iterator가 가리키는 원소에 접근

 

 

🚩 시행착오

연결리스트에 대해 더 공부해야겠다..

1. 컴파일 에러

 for (int j = 0; j < L.length(); j++) {
 	string next = L[j];

위 부분에서 컴파일 에러가 발생하였고, 이유는 아래와 같다.

• L.length()는 size_t 타입을 반환하고, 이는 unsigned int이므로 int와 크기 비교를 할 수 없다. 따라서 앞에 (int)를 붙여주어 캐스트해주면 된다. => 근데 vs로 돌려보면 컴파일 에러가 나지 않는다. 백준 컴파일러는 GCC라 그런듯하다.. 근데 또 이상한 건 vector.size()도 size_t 타입을 반환하는데 똑같은 상황에서 이건 에러가 나지 않는다. 뭐지?
  그리고 L.length()와 L.size()는 동일하다. vector, map 등의 다른 컨테이너와의 일관성을 위해 size가 존재하며, string의 길이에 관해 생각할 때 사람들이 length를 쉽게 떠올리기 때문에, 직관성을 위해 동일한 기능의 length가 있다고 한다.
• L[j]는 char 타입이므로, string 타입에 할당할 수 없다. 따라서 string(1,L[j])로 수정하여 char 타입인 L[j]를 길이가 1인 문자열로 반환하여 next에 할당하였다.

 

2. 런타임 에러 (Segfault)

입력으로 "-"를 받거나 다른 문자를 받을 때, list의 erase, insert 메서드를 사용하였는데 이 부분에서 iterator을 건드리는 게 어려웠다.

else if (next == "-") {
    if (iter != sl.begin())
        sl.erase(--iter);
}
else {
    sl.insert(iter, next);
}

처음에는 위처럼 코드를 작성했다. 여기서 문제는 erase에 있다. erase는 삭제된 요소 뒤의 요소를 가리키는 iterator을 반환하는데, 이를 iter로 받아주지 않으면 iter은 유효하지 않은 위치를 가리킨다.

 

 

💻 코드 (C++)

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

list<string> sl;
list<string>::iterator iter = sl.begin();
int main() {
    
    int x;
    string L;

    cin >> x;
    for (int i = 0; i < x; i++) {
        cin >> L;
        for (int j = 0; j < (int)L.size(); j++) {
            string next = string(1, L[j]);

            if (next == "<") {
                if (iter != sl.begin())
                    iter--;
            }
            else if (next == ">") {
                if (iter != sl.end())
                    iter++;
            }
            else if (next == "-") {
                if (iter != sl.begin())
                    iter = sl.erase(--iter);
            }
            else {
                sl.insert(iter, next);
            }
        }
        for (iter = sl.begin(); iter != sl.end(); iter++) {
            cout << *iter;
        }
        cout << "\n";
        sl.clear();
        iter = sl.begin();
    }
 }