[5397] 키로거

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

분류 : 시뮬레이션, 스택, 링크드리스트

백준 5397 키로거

시뮬레이션, 스택을 이용

---

구현 포인트

1) 직접 구현 시 중간 삽입을 어떻게 할 것인가? 스택 또는 링크드리스트!

처음에 아무생각 없이 코딩했을 때는 중간 삽입에 대한 생각 없이 풀었다..

결과는 물론 시간초과 1초이내에 해낼리가 없다;; 그래서 링크드 리스트와 같은 time complexity를 보이는 deque를 사용하였다.

다른 사람들 코드리뷰를 해보니 스택을 이용하는 다른 방법도 있어서 글을 남기기로 하였다.

우선 내가 푼 코드는 아래와 같다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

#include<iostream> #include<deque> #include<string> using namespace std; int main() {     int t;     string s;     cin >> t;     while (t--) {         deque<char> ans;         int cur = -1;         int limit = -1;         cin >> s;         for (char ch : s) {             switch (ch) {             case '<':                 if (cur != -1) cur--;                 break;             case '>':                 if (cur != limit) cur++;                 break;             case '-':                 if (ans.size() && cur != -1) {                     auto it = ans.begin() + cur;                     ans.erase(it);                     cur--; limit--;                 }                 break;             default:                 if (cur != limit) {                     auto it = ans.begin() + cur+1;                     ans.insert(it, ch);                     cur++;                     limit++;                 }                 else {                     ans.push_back(ch);                     cur++; limit++;                 }                 break;             }         }         for (char ch : ans) {             printf("%c", ch);         }         printf("\n");     } } Colored by Color Scripter

cs

스택으로 푼 사람들의 코드는 아래와 같다.

우선적으로는 left에 저장을 하고, '<'가 나오면 left의 맨 뒷 문자를 stack에 넣는다.

'>'가 나오면 stack에 들어있는 문자를 하나씩 꺼내서 다시 left에 넣어준다.

이런식으로 해도 모든 과정의 O(1)로 효율적으로 답을 구할 수 있다.

#include <iostream>
#include <stack>
#include <string>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        string str, left;
        stack <char> right;
        cin >> str;
        for (char& ch : str) {
            if (ch == '<') {
                if (!left.empty()) {
                    right.push(left.back());
                    left.pop_back();
                }
            }
            else if (ch == '>') {
                if (!right.empty()) {
                    left.push_back(right.top());
                    right.pop();
                }
            }
            else if (ch == '-') {
                if (!left.empty())
                    left.pop_back();
            }
            else
                left.push_back(ch);
 
        }
        while (!right.empty()) {
            left.push_back(right.top());
            right.pop();
        }
        if (!left.empty())
            cout << left << '\n';
    }
}