[Algorithm] 백준 5397 키로거 | C++

※ 5397 키로거

5397번: 키로거 (acmicpc.net)

5397번: 키로거

---

2022.08.26 - [c++/스택] - [Algorithm] Stack(스택) 백준 10799번

[Algorithm] Stack(스택) 백준 10799번

문제 해결 TIP

• 키보드로 타자를 치는 상황을 상상해보자. 모든 타이핑의 기준은 커서이다. 문자의 삽입과 삭제가 모두 커서의 앞에서 이루어진다. 모든 연산이 top에서 이루어지는 스택과 같다고 할 수 있다. 커서=스택의 top위치
• 이 문제에서는 화살표를 통해 커서의 이동이 이루어진다. *커서의 앞에서는 문자 입력 혹은 오른쪽 화살표(>)로 인해 새로운 문자가 삽입되고, 백스페이스와 왼쪽 화살표(<)로 인해 삭제 연산이 일어난다. *커서의 뒤에서는 왼쪽 화살표(<)로 인해 새로운 문자가 삽입되고, 오른쪽 화살표(>)로 인해 기존 문자가 삭제된다. 잘 생각해보면 커서의 앞, 뒤 모두 한 쪽에서만 삽입과 삭제 연산이 이루어지고 있다. 커서의 앞은 오른쪽 끝에서만 연산이 이루어지고, 커서의 뒤는 왼쪽 끝에서만 연산이 이루어진다.
• 따라서 두 개의 스택으로 키보드의 입력을 구현할 수 있다.

문제 해결 풀이

1. 문자 입력시 스택1에 삽입 연산
2. 백스페이스 입력시 스택1에 삭제 연산
3. 왼쪽 화살표 입력시 스택1에서 삭제, 스택2에서 삽입 연산
4. 오른쪽 화살표 입력시 스택2에서 삭제, 스택1에서 삽입 연산

---

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

string stackToString(stack<char> &left, stack<char> &right) {
    // 두 개의 스택을 하나의 문자열로 합치는 함수

    string password;
    // 왼쪽 스택의 top 부터 하나씩 오른쪽 스택에 삽입
    while (!left.empty()) {
        right.push(left.top());
        left.pop();
    }
    // 현재 오른쪽 스택의 top에는 password의 앞글자부터 저장된 상태
    while (!right.empty()) {
        password += right.top();
        right.pop();
    }
    return password;
}

string find_password(string log) {
    stack<char> left;   //커서 이전 내용을 저장
    stack<char> right;  //커서 이후 내용을 저장

    for (int i = 0; i < log.length(); i++) {
        switch (log[i]) {
            case '-':  //현재 커서 앞에 있는 글자 삭제
                if (!left.empty()) {
                    left.pop();
                }
                break;
            case '<':  //커서를 왼쪽으로 이동
                if (!left.empty()) {
                    right.push(left.top());
                    left.pop();
                }
                break;
            case '>':  //커서를 오른쪽으로 이동
                if (!right.empty()) {
                    left.push(right.top());
                    right.pop();
                }
                break;
            default:  //문자인 경우, 입력을 하면 커서보다 왼쪽에 위치하므로 left에 삽입
                left.push(log[i]);
        }
    }

    string password = stackToString(left, right);
    return password;
}

vector<string> solution(int t, vector<string> &log_list) {
    vector<string> answer;
    for (int i = 0; i < t; i++) {
        answer.push_back(find_password(log_list[i]));
    }
    return answer;
}

int main() {
    int t;
    //입력
    cin >> t;
    vector<string> log_list(t, "");

    for (int i = 0; i < t; i++) {
        cin >> log_list[i];
    }
    // 연산
    auto answer = solution(t, log_list);
    // 출력
    for (int i = 0; i < t; i++) {
        cout << answer[i] << '\n';
    }
    return 0;
}