백준 5397 - 키로거 (C++)

 

 

강산이가 입력한 키보드 입력 정보를 토대로 비밀번호를 알아맞추는 문제이다.

 

ABC를 쓰고, 마지막 C를 지우고 D를 입력하면 ABD가 된다.

(ABC-D) -> ABD

 

AB를 쓰고, 왼쪽 화살표를 1회 입력한 뒤 C를 입력하면 ACB가 된다.

(AB<C) -> ACB

 

이처럼, 강산이가 입력한 화살표와 백스페이스, 알파벳 정보를 토대로 최종적으로 입력되는 비밀번호를 출력하면 된다.

 

문제 풀이

이렇게 문자열의 중간에 문자를 삽입하고 삭제하는 등의 문제의 대부분은 스택을 활용하는 문제라고 생각하면 된다.

 

문자열의 경우 중간에 문자를 삽입하거나 삭제하는 연산의 시간복잡도는 O(N)이다. 

이 문제에선 문자열의 최대 길이가 1000000으로 주어졌기 때문에, 하나 삭제하거나 삽입할 때마다 최대 1000000번의 연산을 실행하는 것이다. 그러므로 문자열 자체를 이용해서는 이 문제를 해결할 수 없다.

 

Stack을 활용해서 문제를 푸는 방법을 보자.

 

 

이렇게, 현재 텍스트 커서를 기준으로 양쪽에 2개의 스택을 두고 문제를 해결할 것이다.

 

입력은 <<BP<A>>Cd- 가 들어온다고 가정할 것이다.

 

먼저,<<를 입력받으면 텍스트 커서는 왼쪽으로 한 칸씩 움직여야 할 것이다. 하지만, 현재 아무런 문자도 입력되지 않은 상황이라 텍스트 커서를 아무리 왼쪽으로 옮겨도 텍스트 커서는 움직이지 않는다.

 

그러므로, <<는 아무런 변화를 주지 않는다.

 

다음, B를 입력받았다고 해보자. 우리가 키보드에 A를 쳐보면, 텍스트 커서는 A의 바로 뒤에 붙어있는 것을 볼 수 있다.

그러므로, 입력반은 문자도 이와 동일하게 텍스트 커서의 앞에 입력해주자.

 

LeftStack에 문자를 삽입하는 것을 입력하는 것이라고 가정하겠다. LeftStack에 B를 삽입해주자.

스택은 이렇게 변화하게 된다.

다음 입력 P에 대해서도 동일하게 실행해보자.

스택은 위 그림과 같아진다.

 

다음 입력은 < 이다. 처음 <를 입력받았을 때엔 문자가 아무것도 입력되어 있지 않았기 때문에 텍스트 커서가 움직이지 않았지만, 이번엔 BP가 입력되어 있기 때문에, 텍스트 커서를 왼쪽으로 한 칸 움직이면 텍스트 커서는 B와 P사이에 위치하게 된다. 그러므로 스택은 아래와 같이 변하게 된다.

 

LeftStack은 텍스트 커서를 기준으로 왼쪽에 있는 문자들이며, RightStack은 텍스트 커서 기준으로 오른쪽에 있는 문자들인 셈이다. 그러므로, LeftStack의 가장 위의 원소를 빼서 RightStack으로 넣어주는 것을 텍스트 커서를 왼쪽으로 한 칸 움직인 것이라고 할 수 있는 것이다.

 

다음 입력 A에 대해서도 위에서 보았던 과정을 그대로 거쳐주자.

입력받은 문자는 텍스트 커서를 기준으로 위치하게 되므로, A는 위처럼 LeftStack에 삽입된다

 

다음 입력은 >이다. 텍스트 커서를 우측으로 한 칸 이동하는 것이다.

이는 <와 반대로 하면 된다. RightStack의 top을 LeftStack으로 넣어주자.

위의 그림과 같은 상태에서 다시 >를 입력받게 된다면, 텍스트 커서는 이미 문자의 마지막에 위치하기 때문에 아무런 변화가 없다. 그대로, 다음 입력을 받아주면 된다.

 

다음 입력은 C이다. C를 입력받으면, LeftStack에는 C가 추가될 것이다. 다음 d에 대해서도 똑같이 LeftStack에 d가 추가될 것이다.

스택은 위 그림과 같아질 것이다.

 

마지막으로, -입력이 들어온다면 텍스트 커서 바로 앞의 문자를 지워주면 된다.

그러므로, LeftStack의 top을 제거해주면 된다.

최종적으로 스택은 위와 같아진다.

 

그대로, LeftStack과 RightStack에 있는 문자열을 순서대로 string에 옮겨서 출력해주면 된다.

 

여기서 유의할 점은, 우리가 출력해야 하는 답과 LeftStack에서 꺼내는 순서가 반대라는 것이다.

LeftStack에서 차례대로 원소를 꺼내면, CPAB가 된다. 하지만, 우리가 원하는 답은 BAPC이다. 이를 고려하여 순서를 바꿔주어야 한다.

 

반면, RightStack은 위 경우에서는 남아있는 문자가 없기 때문에 확인할 수 없지만 RightStack은 꺼내는 순서가 문자열의 순서와 일치하기 때문에 RightStack의 원소는 뒤집지 않고 그대로 저장하여주면 된다.

 

풀이 코드

int NumCase = 0;
std::cin >> NumCase;

std::vector<std::string> Answers(NumCase);

 

테스트 케이스의 수를 입력받고, 답을 저장할 배열을 선언해주자.

 

std::string Input;
std::cin >> Input;

std::stack<char> LeftStack;
std::stack<char> RightStack;

 

이후, 각 케이스에 대해 문자열을 입력받고 두개의 스택을 선언하여 주었다.

 

for (int i = 0; i < Input.size(); i++)
{
    if (Input[i] == '<')
    {
        if (LeftStack.size() > 0)
        {
            RightStack.push(LeftStack.top());
            LeftStack.pop();
        }
    }
    else if (Input[i] == '>')
    {
        if (RightStack.size() > 0)
        {
            LeftStack.push(RightStack.top());
            RightStack.pop();
        }
    }
    else if (Input[i] == '-')
    {
        if (LeftStack.size() > 0)
        {
            LeftStack.pop();
        }
    }
    else
    {
        LeftStack.push(Input[i]);
    }
}

 

다음은 위에서 말했던 과정을 그대로 코드로 옮긴 것이다.

 

<를 입력받으면 LeftStack의 top을 RightStack으로 옮겨준다. 다만, LeftStack의 size가 0이라면 아무런 일도 발생하지 않는다.

 

>도 반대로 작동할 뿐 똑같이 구현하였다.

 

-를 입력받으면, LeftStack의 top을 지워준다.

 

알파벳을 입력받으면 그대로 LeftStack에 삽입하여 준다.

 

int LeftSize = LeftStack.size();
int RightSize = RightStack.size();

std::string Answer(LeftSize + RightSize, '\0');
for (int i = 0; i < LeftSize; i++)
{
    Answer[LeftSize - 1 - i] = LeftStack.top();
    LeftStack.pop();
}

for (int i = LeftSize; i < Answer.size(); i++)
{
    Answer[i] = RightStack.top();
    RightStack.pop();
}

Answers[Case] = Answer;

 

모든 과정이 끝나고, Stack에 있는 문자들를 답으로 옮겨주어야 한다.

위에서 말했듯이, LeftStack은 순서가 반대이기 때문에 Answer의 뒤쪽부터 데이터를 삽입해주고 있다.

 

그리고, LeftStack의 문자를 모두 저장한 뒤, RightStack의 문자를 그 뒤에 추가로 저장해주고 있다.

이 때, RightStack의 순서는 반대가 아니기 때문에 그대로 저장해주면 된다.

 

이렇게 구한 답을 마지막에 출력해주면 문제는 끝이다.

 

코드 전문

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

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int NumCase = 0;
    std::cin >> NumCase;

    std::vector<std::string> Answers(NumCase);

    for(int Case = 0; Case < NumCase; Case++)
    {
        std::string Input;
        std::cin >> Input;

        std::stack<char> LeftStack;
        std::stack<char> RightStack;

        for (int i = 0; i < Input.size(); i++)
        {
            if (Input[i] == '<')
            {
                if (LeftStack.size() > 0)
                {
                    RightStack.push(LeftStack.top());
                    LeftStack.pop();
                }
            }
            else if (Input[i] == '>')
            {
                if (RightStack.size() > 0)
                {
                    LeftStack.push(RightStack.top());
                    RightStack.pop();
                }
            }
            else if (Input[i] == '-')
            {
                if (LeftStack.size() > 0)
                {
                    LeftStack.pop();
                }
            }
            else
            {
                LeftStack.push(Input[i]);
            }
        }

        int LeftSize = LeftStack.size();
        int RightSize = RightStack.size();

        std::string Answer(LeftSize + RightSize, '\0');
        for (int i = 0; i < LeftSize; i++)
        {
            Answer[LeftSize - 1 - i] = LeftStack.top();
            LeftStack.pop();
        }

        for (int i = LeftSize; i < Answer.size(); i++)
        {
            Answer[i] = RightStack.top();
            RightStack.pop();
        }

        Answers[Case] = Answer;
    }

    std::copy(Answers.begin(), Answers.end(), std::ostream_iterator<std::string>(std::cout, "\n"));

    return 0;
}