백준 5397번 키로거

문제 링크입니다: https://www.acmicpc.net/problem/5397

스택을 두개 사용하여 푸는 흥미로운 문제였습니다.

알고리즘은 아래와 같습니다.

1. 결과를 저장하는 result와 화살표 입력시 필요한 temp 스택을 각각 정의합니다.

2. 왼쪽 화살표를 입력하는 경우 result의 top에 있는 문자를 temp에 push하고 result에서 pop합니다.

3. 오른쪽 화살표를 입력하는 경우 temp의 top에 있는 문자를 result에 push하고 temp에서 pop합니다.

4. 백스페이스를 하는 경우 단순히 result에서 한번 pop합니다.

5. 2, 3, 4번 외에는 단순히 result에 push 합니다.

6. 반복문을 탈출했을 때, temp에 여전히 문자들이 남아있을 수 있습니다. 따라서 temp에 있는 문자들을 전부 result에 push합니다.

7. stack은 LIFO(Last In First Out) 구조이기 때문에 거꾸로 출력을 해줘야합니다!

#include <iostream>

#include <string>

#include <stack>

#include <algorithm>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        int test_case;

        cin >> test_case;

 

        for (int t = 0; t < test_case; t++)

        {

                 string s;

                 cin >> s;

 

                 stack<char> result; //결과

                 stack<char> temp; //화살표 입력 시 필요

                 for (int i = 0; i < s.length(); i++)

                 {

                         if (s[i] == '<')

                         {

                                 if (!result.empty())

                                 {

                                          temp.push(result.top());

                                          result.pop();

                                 }

                         }

                         else if (s[i] == '>')

                         {

                                 if (!temp.empty())

                                 {

                                          result.push(temp.top());

                                          temp.pop();

                                 }

                         }

                         else if (s[i] == '-')

                         {

                                 if (!result.empty())

                                          result.pop();

                         }

                         else

                         {

                                 result.push(s[i]);

                         }

                 }

 

                 while (!temp.empty())

                 {

                         result.push(temp.top());

                         temp.pop();

                 }

 

                 string answer;

                 while (!result.empty())

                 {

                         answer += result.top();

                         result.pop();

                 }

                 //LIFO이기 떄문에

                 reverse(answer.begin(), answer.end());

                 cout << answer << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~