[C++] 백준 5397 키로거

www.acmicpc.net/problem/5397

5397번: 키로거

 

1. 서론

 

메모리 때문에 코드를 몇 번이나 다시 짰는데도... 안돼서 답을 슬쩍 들춰보고야 겨우 푼... 문제

 

2. 문제 풀이

 

비밀번호를 입력하는데 그 동작을 모두 문자열로 기록하는 키로거라는 프로그램이 있다. 그 동작은 문자열로 저장되고 '<', '>', '-'는 각각 화살표 버튼과 딜리트 버튼을 뜻한다. 화살표의 경우는 방향대로 한 칸 이동하며 딜리트 버튼은 현재 커서가 있는 문자를 지운다.

 

커서의 위치가 중요하다고 생각해서 처음에는 string + 포인터로 쓸 변수 하나로 코드를 짰지만 실패했다. 그리고 이 문제는 스택으로 풀어야 한다는 힌트를 보고 스택으로 풀긴 했는데 스택의 size가 바뀌는 대로 계속 새로 불러오는 바람에 시간이 초과돼서 또 실패했다. 

 

그래서 결국 어떤 논리로 푸는건가 슬쩍 봤더니 코드를 다 읽어보진 않았지만 변수 이름들을 보니까 스택 두 개를 놓고 왼쪽, 오른쪽으로 문자열 값을 옮기며 코드가 진행되는 것을 봤다. 난 삽질을 너무 많이 해서 (너무 어렵게 풀어서) 설마 이렇게 해도 모든 케이스에서 다 성립한다고? 생각했는데 진짜 됐다. 내가 푼 코드는 내가 본 답과는 방향이 살짝 다르긴 한데 아마 핵심 논리는 똑같을 것이다. (답 코드를 정확히 안 봐서 잘 모른다)

 

논리는 간단하다. 문자열을 스택에 삽입하는데 오른쪽 스택에 값을 넣는 것을 기본으로 한다. 그러다 '<'가 나오면 오른쪽 스택의 top의 값을 왼쪽 스택에 넣는다. '>'의 경우는 왼쪽 스택의 top의 값을 오른쪽 스택에 넣는다. 커서가 이동하는 방향을 따라서 그 커서가 가리키는 값이 스택의 top에 올라오게끔 하는 것이다. 생각지도 못한 독특한 발상이다...

 

3. 코드 설명

 

#include <stack>
#include <string>
#include <iostream>

using namespace std;

int main()
{
    int n, i, j;
    string k, t;
    stack<char> r, l;

    cin >> n;

    for (i = 0; i < n; i++)
    {
        cin >> k;

        for (j = 0; j < k.length(); j++)
        {
            if (k[j] == '>' && !l.empty())
            {
                r.push(l.top());
                l.pop();
            }
            
            if (k[j] == '<' && !r.empty())
            {
                l.push(r.top());
                r.pop();
            }
            
            if (k[j] == '-' && !r.empty())
                r.pop();
            
            if (k[j] != '-' && k[j] != '<' && k[j] != '>')
                r.push(k[j]);
        }

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

        while(!r.empty())
        {
            t += r.top();
            r.pop();
        }

        for (j = t.length() - 1; j >= 0; j--)
            cout << t[j];
        cout << endl;
        t.clear();
    }
}

 

문자열을 입력받고 오른쪽 스택 r에 그 값을 넣는다. 

만약 '>'가 나오면 왼쪽 스택의 top값을 오른쪽 스택에 넣고, 왼쪽 스택은 pop해준다.

만약 '<'가 나오면 위의 경우를 반대로 한다.

만약 '-'가 나오는 경우 오른쪽 스택이 메인 문자열이기 때문에 오른쪽 스택의 top(커서가 가리키는 부분)을 pop 한다.

그리고 문자열을 전부 다 훑고 반복문을 빠져나왔을 때 보조 역할을 하던 왼쪽 스택의 남아있는 값을 전부 오른쪽 스택으로 넣고 스택은 역순으로 쌓이기 때문에 top을 전부 꺼내서 역으로 출력해주면 원래의 문자열 순서대로 출력할 수 있다.

 

모르는 문제를 적당히 포기할 수 있는 용기가 필요하다... (괜히 오기로 며칠 동안 시간 낭비함 ㅎ,, 물론 스스로 떠올리면 좋기야 하겠지만,,)

 

+ 테스트 케이스 모음

m.blog.naver.com/PostView.nhn?blogId=knight7024&logNo=221196665404&proxyReferer=https:%2F%2Fwww.google.com%2F

[백준] 5397번: 키로거