[BKD/C++] 5397::키로거 KeyLogger

 

5397번: 키로거

키로거

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	53922	15157	10356	26.615%

문제

창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다.

 

키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다. 

 

강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오. 강산이는 키보드로 입력한 키는 알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표이다.

 

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입력했다면, '-'가 주어진다. 이때 커서의 바로 앞에 글자가 존재한다면, 그 글자를 지운다. 화살표의 입력은 '<'와 '>'로 주어진다. 이때는 커서의 위치를 움직일 수 있다면, 왼쪽 또는 오른쪽으로 1만큼 움직인다. 나머지 문자는 비밀번호의 일부이다. 물론, 나중에 백스페이스를 통해서 지울 수는 있다. 만약 커서의 위치가 줄의 마지막이 아니라면, 커서 및 커서 오른쪽에 있는 모든 문자는 오른쪽으로 한 칸 이동한다.

 

출력

각 테스트 케이스에 대해서, 강산이의 비밀번호를 출력한다. 비밀번호의 길이는 항상 0보다 크다.

---

예제 입력 1 복사

2
<<BP<A>>Cd-
ThIsIsS3Cr3t

예제 출력 1 복사

BAPC
ThIsIsS3Cr3t

 

---

후기

이번 문제는 머리 싸맨 시간이 길었는데, 생각보다 문제 해결 방법이 쉬웠다.

 

코드의 큰 플로우는 다음과 같다.

1. 문자열을 입력 받는다.
2. 입력 받은 문자열을 iterator로 처음부터 읽어들인다.
3. 읽어 들이며 알파벳은 storage 리스트에 저장한다.
4. 읽으며 조건 문자들('-', '<', '>')에 대한 행동을 처리한다.
   1. '-'를 만나면 storage에 시작점이 아닌 이상 현재 위치 바로 직전 값을 제거한다.
   2. '<'를 만나면 시작점이 아닌 이상 다음 입력 값 위치(iterator)를 한 원소 앞으로 간다.
   3. '>'를 만나면 끝점이 아닌 이상 다음 입력 값 위치(iterator)를 한 원소 뒤로 간다.
5. storage리스트에 담겨진 문자들을 출력한다.

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

string KeyLoggerList(string input);

int main(void) {
    int loop;
    cin >> loop;
    
    while (loop--) {
        string input;
        cin >> input;
        cout << KeyLoggerList(input) << endl;
    }

    return 0;
}

string KeyLoggerList(string input) {
    string result;
    list<char> storage;
    list<char>::iterator curser = storage.begin();

    for (auto character : input){
        if (character == '-'){
            if (curser != storage.begin())
                curser = storage.erase(--curser);
            }
        else if (character == '<'){
            if (curser != storage.begin())
                curser--;
            }
        else if (character == '>'){
            if (curser != storage.end())
                curser++;
            }
        else{
            storage.insert(curser, character);
        }
    }

    for (auto a : storage) result += a;
    
    return result;
}

 

queue와 stack에는 iterator가 없어서 사용 못한다.

그러니 리스트랑 놀아야하는데, 코드를 작성하다 왜 string을 배열처럼 사용하여 리스트를 사용할 공간을 아끼지 않는 걸까 생각했다.

 

그래서 뻘짓을 시작했다.

 

우선 결론만 말하면, 하지마라. string으로 불가능한 것은 아니라 본다. 하지만, 신경 써야할 부분이 훨씬 늘어났다.

 

string에서 iterator를 추출하여 사용할 수 있다.

그렇지만, 동작하는 방식은 리스트와 달랐다.

 

우선 List는 기본적으로 iterator가 내부 원소의 가장 뒤 쪽에 자리 잡는다. 3개의 원소가 입력되면 마지막 원소 뒤에 iterator가 자리잡는 것이다.

하지만, string의 iterator는 1개의 원소가 입력되면 해당 원소 자리에 iterator가 위치한다.

 

이걸 쉽게 보면 다음과 같다. 그리고 이로 인해 발생하는 차이 또한 있다.

 

string 문자 제거

// 크기가 3인 list와 string
// * = iterator 위치
List A = [A][B][C][*], string A = [A][B][*C]

// iterator의 -1 위치의 원소 제거하기
List A = [A][B][C][*], string A = [A][B][*C]
                ^ 'C'제거             ^ 'B'제거

위와 같이 List는 마지막 위치에서 앞의 원소를 제거하면 마지막 원소를 제거한다. 이때, erase함수가 반환하는 itearator 위치 값은 지워진 원소의 다음 주소 값이 된다.

 

반면 string은 마지막 위치에서 앞의 원소를 제거하면 마지막 원소가 아닌 그 앞의 원소를 제거한다. 즉, 제거할 자리의 포인터를 따로 생성하고 커서는 다른 곳으로 이동시켜야 현재 원소를 지울 수 있게된다.

 

string 문자 입력

// 2번째 원소에 커서가 존재
string A = [A][*B][C]
// 문자 'D' 입력
string A = [A][D][*B][C]

또한, string에 새로운 문자를 넣는 것도 크기가 0보다 큰 문자열에 입력값을 넣는 경우, 커서의 위치에 문자를 넣게 되면 문자가 뒤에 생성되는 것이 아닌 앞에 생성되어 버린다.

 

 

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

string KeyLoggerString(string input);

// asdf<<asdf>>asdf = asasdfdfasdf

int main(void) {
    int loop;
    cin >> loop;
    
    while (loop--) {
        string input;
        cin >> input;
        cout << KeyLoggerString(input) << endl;
    }

    return 0;
}


// <summary> String Keylogger
string KeyLoggerString(string input) {
    // String iterator는 list와 다르게 원하는 위치에서 실행된다.
    // 0. "ABC" 문자 입력 ('$' = 커서 위치)
    // list = ABC"", string = AB"C"
    // 1. 커서의 앞 문자 erase함수로 제거하기
    // list = AB"", string = A"C"
    // 2. 신규 문자 'T'를 insert함수로 넣기
    // list = ABT"", string = AT"C"
    // ++++++++++ 결론 ++++++++++
    // string을 바로 사용하여 list와 같이 만들 수는 있겠지만
    // 그로인해 추가적으로 연산처리를 해야하는 것들이 많아진다.
    // 코드 더러워진다. 하지말자.
    string result = "";
    string::iterator curser = result.begin();
    
    for (auto character : input){
        if (character == '-'){
            if (curser != result.begin()) {
                string::iterator temp = curser--;
                result.erase(temp);
            }
        }
        else if (character == '<'){
            if (curser != result.begin()) {
                curser--;
            }
        }
        else if (character == '>'){
            if (curser != --result.end()) {
                curser++;
            }
        }
        else{
            if (result.size() > 0) curser++;
            result.insert(curser, character);
        }
    }

    return result;
}