[algorithm] 백준 5397번 키로거

처음에 문제를 풀 때

리스트에 입력 문자열을 넣고

리스트를 순회하면서 반복자를 리스트에 두고 각 문자들을 확인하여 vector에 반영하는 식으로 하려했다

 

하지만 이 경우

벡터는 반복자를 사용할 수 있지만

중간 삽입 삭제가 O(n)이여서 비효율적이다

 

결국 결과 출력할 리스트에서 반복자를 두고 조작하는 방식이 효율적이다

또한 그렇게되면 리스트 2개가 아닌 1개만 사용해도 된다

#include <iostream>
#include <list>
#include <string>
using namespace std;

int main() {
    int n;
    string s;
    list<char> l;

    cin >> n;
    for(int tmp=0; tmp<n; tmp++)
        {
            l.clear();
            cin >> s;
            auto p = l.begin();
            for(int i=0; i<s.length(); i++)
                {
                    if(s[i] == '<')
                    {
                        if(p != l.begin()) p--;
                    }

                    else if(s[i] == '>')
                    {
                        if(p != l.end()) p++;
                    }

                    else if(s[i] == '-')
                    {
                        if(p != l.begin()) p = l.erase(--p);
                    }

                    else
                    {
                        l.insert(p,s[i]);
                    }

                }

            for(char c : l) cout << c;
            cout << "\n";
        } 
    return 0;
}

 

string 타입도 인덱스 접근이 가능하기에

굳이 입력값을 받을 list를 하나 더 만들지 않아도 되는 것이다

 

간단해 보이지만

구현 방식에 깊이가 있던 문제였다

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--) {
        stack<char> s1;
        stack<char> s2;
        string L;
        cin >> L;
        for (char letter : L) {
            if (letter == '<') {
                if (s1.empty()) continue;
                s2.push(s1.top());
                s1.pop();
            } else if (letter == '>') {
                if (s2.empty()) continue;
                s1.push(s2.top());
                s2.pop();
            } else if (letter == '-') {
                if (s1.empty()) continue;
                s1.pop();
            } else {
                s1.push(letter);
            }
        }

		while (!s1.empty()) {
    		s2.push(s1.top());
    		s1.pop();
		}

		while (!s2.empty()) {
    		cout << s2.top();
    		s2.pop();
		}


        cout << '\n';
    }

    return 0;
}

 

스택으로 풀이한 기발한 풀이가 있어 소개해보려고 한다

두 스택 사이에 커서가 있다고 생각하고

커서의 왼쪽에 스택1 오른쪽에 스택2라고 설정한다

 

예를 들어 '<'를 입력받았다고 했을 때

[a,b,c] | [x,y,z]
[a,b] | [c,x,y,z]

왼쪽 스택의 top을 오른쪽 스택에 push하고

왼쪽 스택의 top은 pop하는 구조다

 

'-'와 일반 알파벳 입력 모두 왼쪽 문자열에서 처리한다

 

최종적으로 모든 입력을 받았다면

출력을 해야하는데

왼쪽은 그대로 출력한다면 역순으로 나오므로

오른쪽 스택에 보내고

오른쪽 스택에서 하나씩 출력하면된다