[백준] #5397 키로거

문제 소개
https://www.acmicpc.net/problem/5397

 
키로커는 다음과 같은 동작을 시뮬레이션하는 문제이다.
 
입력은 알파벳 대소문자, 숫자, 그리고 특수 키(-, <, >)로 이루어진다.

• - : 백스페이스(커서 앞의 문자 삭제)
• < : 커서를 왼쪽으로 이동
• > : 커서를 오른쪽으로 이동

이 과정을 모두 거친 후 최종적으로 화면에 남는 문자열을 출력하면 된다.

 
내 풀이
 

처음에 떠올린 방법은 문자열을 통째로 std::list에 담아두고, 그 다음에 -, <, > 같은 특수 키를 따로 처리하는 방식이었다.

#include <iostream>
#include <list>

using namespace std;

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

    string init;
    cin >> init;
    list<char> L; 
    for (auto c : init)
        L.push_back(c);
    auto t = L.end();

    if (c == '-' && !L.empty())
        t = L.erase(t);
    if (c == '<')
        t--;
    if (c == '>')
        t++;

    for (auto c : L)
        cout << c;
}

 
하지만 이 코드는 컴파일조차 되지 않았다.
 

트러블슈팅

1. 문자열 전체를 한 번에 list에 넣다 보니 -, <, >가 동작하지 않았다.
2. 커서가 맨 앞이나 맨 뒤에 있을 때를 고려하지 않았다.

즉, 입력을 처음부터 끝까지 읽으면서 그때그때 동작을 수행해야 했다.
 
여기서 핵심은 입력 문자를 두 가지로 나누어 생각하는 것이다.

• c(-, <, >): 커서 이동이나 삭제 같은 특수 동작을 수행해야 함
• t(그 외 문자): 단순히 현재 커서 위치에 삽입하면 됨

이를 바탕으로 수정해서 제출한 코드는 아래와 같다.

#include <iostream>
#include <list>

using namespace std;

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

    int n;
    cin >> n;

    for (int i=0; i<n; i++) {
    string init;
    cin >> init;
        
    list<char> L; 
    auto t = L.end();

    for (auto c : init) {
        if (c == '-' && t != L.begin())
            t = L.erase(--t);
        else if (c == '-' && t == L.begin())
            t = L.erase(t);
        else if (c == '<') {
            if (t != L.begin())
                t--;
        }
        else if (c == '>') {
            if (t != L.end())
                t++;
        }
        else 
            L.insert(t, c);
        }
        
    for (auto c : L)
        cout << c;
        cout << '\n';
    }
}

 
하지만 제출한 코드는 틀렸다고 나왔다.

여러 테스트케이스를 직접 입력해보니 문제의 원인을 알 수 있었다.
바로 백스페이스(-)가 가장 먼저 입력된 경우였다.

if (c == '-' && t != L.begin()) {
    t = L.erase(--t);
}
else if (c == '<') {
    ...
}
else if (c == '>') {
    ...
}
else {
    L.insert(t, c);
}

 
이렇게 처리하면 백스페이스가 입력의 첫 글자로 들어온 경우, 삭제가 안 되고 오히려 '-'가 리스트에 삽입되는 문제가 있었다.
이를 방지하기 위해 '-'는 무조건 먼저 검사하고, 커서가 맨 앞에 있으면 그냥 무시하도록 수정했다.

if (c == '-') {              // '-'가 들어오면 무조건 이 블록 안에서 처리
    if (t != L.begin())      // 커서가 맨 앞이 아니면
        t = L.erase(--t);    // 커서 앞 문자 삭제
}                            // 커서가 맨 앞이면 아무것도 안함

 

최종 코드

#include <iostream>
#include <list>

using namespace std;

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

    int n;
    cin >> n;

    for (int i=0; i<n; i++) {
    string init;
    cin >> init;
        
    list<char> L; 
    auto t = L.end();

    for (auto c : init) {
        if(c == '-') {
            if (t != L.begin()) t = L.erase(--t);
        }
        else if (c == '-' && t == L.begin()) {
            t = L.erase(t);
        }
        else if(c == '<') {
            if(t != L.begin())
                t--;
        }
        else if(c == '>') {
            if(t != L.end())
                t++;
        }
        else
            L.insert(t, c);
        }
        
    for (auto c : L)
        cout << c;
        cout << '\n';
    }
}