[스택/구현] BAEKJOON 5397번 '키로거'문제(c++/python)

문제 : www.acmicpc.net/problem/5397

5397번: 키로거

 

 

• 문제 해결 아이디어

    1.   stack을 두개 사용하여 가운데에 cursor가 있다고 생각한다.

    2.  '-' 가 입력되면 left stack에서 pop을 한다.

 

    3.  '<'가 입력되면 커서가 왼쪽으로 옮겨가야 되므로, left stack의 top값을 빼서 right stack으로 옮긴다.

 

    4.  '>'가 입력되면 커서가 오른쪽으로 옮겨가야 되므로, right stack의 top값을 빼서 left stack으로 옮긴다.

 

    5.  3,4번진행 중 stack이 비어있어 뺄 수 있는 top이 없다면 넘어간다.

 

    6.  일반 문자가 입력되면 left stack에 넣어준다.

 

    7.  문자열을 모두 읽은 후 left stack부터 right stack까지 출력해준다. (위 모양대로 뒤집어지지않게 출력해준다.)

 

 

 

• python

test_case = int(input())

for _ in range(test_case):
    left_stack = []
    right_stack = []

    data = input()

    for i in data:
        if i == '-':
            if left_stack:
                left_stack.pop();
        elif i == '<':
            if left_stack:
                right_stack.append(left_stack.pop())
        elif i == '>':
            if right_stack:
                left_stack.append(right_stack.pop())
        else:
            left_stack.append(i)

    left_stack.extend(reversed(right_stack))  # right_stack의 top부터 이어서 저장하기 위해 reversed 해준다.
    print(''.join(left_stack))                # 공백없이 left_stack의 값을 하나의 문자열로 합쳐서 출력한다.

 

• c++

    최초 result_stack이 있고, 커서가 왼쪽으로 옮겨갈 때 마다 result_stack의 top요소를 tmp_stack에 쌓는다.

    (위 아이디어로 보면 result_stack == left_stack, tmp_stack == right_stack)

    각 test_case끼리 영향을 주지 않도록, stack에서 top을 읽었으면 반드시 pop을 해준다.

 

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main(){
    
    int test_case;
    cin >> test_case;
    
    while(test_case){
        
        string input;
        stack<char> result_stack;
        stack<char> tmp_stack;
        int i = 0;
        
        cin >> input;
        int L = input.length();
        
        while(L){
           
            if(input[i] == '<'){
                
                if(result_stack.empty())
                    ;
                else{
                    tmp_stack.push(result_stack.top());
                    result_stack.pop();
                }
            }
                
            else if(input[i] == '>'){
                
                if(tmp_stack.empty())
                    ;
                else{
                    char tmp;
                    tmp = tmp_stack.top();
                    tmp_stack.pop();
                    result_stack.push(tmp);
                }
            }
            
            else if(input[i] == '-'){
                
                if(result_stack.empty())
                    ;
                else
                    result_stack.pop();
            }
            
            else{
                result_stack.push(input[i]);
            }
            
            i++;
            L--;
        }
        
        while(!tmp_stack.empty()){
            char tmp;
            tmp = tmp_stack.top();
            result_stack.push(tmp);
            tmp_stack.pop();
        }
        
        
        int result_len = result_stack.size();
        vector<char> result;
        
        
        while(result_len){
            result.push_back(result_stack.top());
            result_stack.pop();
            result_len--;
        }
        
        for(int i = result.size()-1 ; i>=0 ; i--){
            cout << result[i];
        }
        
        cout << "\n";
        
        
        test_case--;
    }
    
    return 0;
}