[baekjoon] 5397 키로거 실버2

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

설명

• 연결 list를 활용하는 문제로 시간복잡도를 고민하며 풀기에 좋은 문제라고 생각함
• 입력 값에 따라 어떻게 문자가 수정되는지를 판별
• 비슷한 문제 : https://www.acmicpc.net/problem/1406

---

해답

#include <iostream>
#include <list>

using namespace std;

int main() 
{
    int n;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        string str;
        cin >> str;

        list<char> arr;
        auto cursor = arr.begin();

        for(int j=0;j<str.size();j++)
        {
            if(str[j] == '<')
            {
                if(cursor != arr.begin())
                    cursor--;
            }
            else if(str[j] == '>')
            {
                if(cursor != arr.end())
                cursor++;
            }
            else if(str[j] == '-')
            {
                if(cursor != arr.begin())
                cursor = arr.erase(--cursor);
                
            }
            else
            {
                cursor = arr.insert(cursor,str[j]);
                cursor++;
            }

        }
        for(auto a:arr)
        {
            cout<<a;
        }
        cout << endl;
    }
   
}

---

고찰

• 최대 입력이 1,000,000이라서 무조건 for문을 하나만 사용해야한다는 강박이 있었는데, 2중 for문으로 하나로 해결할 수 있다는 사실을 되새겼음.
• list의 빠른 삽입과 삭제 속도를 다시 한번 체감했음.