[BOJ] 백준 5397 키로거

출처: https://www.acmicpc.net/problem/5397

 Input 

2

<<BP<A>>Cd-

ThIsIsS3Cr3t

 

 Output 

BAPC

ThIsIsS3Cr3t

 

두 개의 스택을 이용해 구현합니다.

[C++] [STL] Stack 

[C++] [STL] Stack

 

실제 암호를 저장하기 위한 스택과 화살표(『<』 『>』) 처리를 위한 스택

- 왼쪽 화살표: result 스택에 있는 원소를 pop하여 temp 스택에 push

- 오른쪽 화살표: temp 스택에 있는 원소를 pop하여 result 스택에 push

- 백스페이스(-): result 스택에 있는 원소를 pop

- 그 외의 경우에는 result 스택에 push

※ C++에서는 pop()이 top이 가리키고 있는 원소를 반환하지 않으므로 top() 이용.

 

입력되는 경우에 따라서는 temp 스택에 원소가 남은 채로 반복문이 끝나는데,

이  경우, temp에 남은 원소를 result에 모두 push합니다.

정답을 출력할 때는 result 스택에 있는 원소를 pop하여 다시 거꾸로 출력.(← LIFO 구조)

 

시뮬레이션

▶ <<BP<A>>Cd-

왼쪽 화살표가 처음 2개 주어져있지만, result 스택이 비워져 있으므로 변화 X

result = [] / temp = []

 

▶ <<BP<A>>Cd-

B와 P를 차례대로 result 스택에 push

result = [B P] / temp = []

 

▶ <<BP<A>>Cd-

왼쪽 화살표를 입력받았을 때, result 스택에 원소가 존재하므로

result 스택 top() 원소를 temp 스택에 push 해주고 result 스택에서는 pop

result = [B] / temp = [P]

 

▶ <<BP<A>>Cd-

A 문자를 result 스택에 push

result = [B A] / temp = [P]

 

▶ <<BP<A>>Cd-

오른쪽 화살표를 입력받았을 때, temp 스택에 원소가 존재하므로

temp 스택 top() 원소를 result 스택에 push 해주고 temp 스택에서는 pop

result = [B A P] / temp = []

 

▶ <<BP<A>>Cd-

오른쪽 화살표를 입력받았을 때, temp 스택이 비워져 있으므로 변화 X

result = [B A P] / temp = []

 

▶ <<BP<A>>Cd-

C와 d를 차례대로 result 스택에 push

result = [B A P C d] / temp = []

 

▶ <<BP<A>>Cd-

백스페이스(-)가 입력되었을 때, result 스택에 원소가 존재하므로 pop

result = [B A P C] / temp = []

---

#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
 
stack<char> result, temp;
int main(void){
    int TC;
    cin >> TC;
    while(TC-- > 0){
        string str;
        cin >> str;
 
        for (int i = 0; i < str.length(); ++i){
            switch (str[i]){
            case '<':
                if (result.empty()) break;
                temp.push(result.top());
                result.pop();        
                break;
            case '>':
                if (temp.empty()) break;
                result.push(temp.top());
                temp.pop();
                break;
            case '-':
                if (result.empty()) break;
                result.pop();
                break;
            default:
                result.push(str[i]);
                break;
            }
        }
 
        // temp 스택에 원소가 남아있는 경우
        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 << endl;
    }
}