에디터 (feat. 백준, 1406번)

에디터
https://www.acmicpc.net/problem/1406

1406번: 에디터

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <cstring>
#include <list>
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    // string str, tmp;
    // register int N, pos;
    // cin >> str >> N;
    // pos = str.size();
    // for(register int n = 0; n < N; ++n){
    //     cin >> tmp;
    //     if(!tmp.compare("L")){
    //         if(pos > 0)
    //             pos -= 1;
    //     }
    //     else if(!tmp.compare("D")){
    //         if(pos < str.size())
    //             pos += 1;
    //     }
    //     else if(!tmp.compare("B")){
    //         if(pos > 0)
    //             pos -= 1, str = str.erase(pos, 1);
    //     }
    //     else if(!tmp.compare("P")){
    //         cin >> tmp;
    //         str.insert(pos, tmp);
    //         pos += tmp.size();
    //     }
    // }
    // cout << str;
    string tmp;
    list<char> ans;
    register int N;
    cin >> tmp >> N;
    for(auto& v : tmp)
        ans.push_back(v);
    list<char>::iterator pos = ans.end();
    for(register int n = 0; n < N; ++n){
        cin >> tmp;
        if(!tmp.compare("L")){
            if(pos != ans.begin())
                --pos;
        }
        else if(!tmp.compare("D")){
            if(pos != ans.end())
                ++pos;
        }
        else if(!tmp.compare("B")){
            if(pos != ans.begin()){
                pos = ans.erase(--pos);
            }
        }
        else if(!tmp.compare("P")){
            cin >> tmp;
            pos = ans.insert(pos, tmp.at(0));
            ++pos;
        }
    }
    for(auto& v : ans)
        cout << v;
    return 0;
}
// *&)*@*

 

1. 문제에서 주어진 요구사항에 따라 구현하는 문제입니다.
2. 단, 주석과 같이 string의 erase와 insert는 시간복잡도로 인해 시간 초과 판정을 받게 되므로 이를 해결할 수 있는 방법으로 구현해야 합니다. (저는 양방향 리스트 자료구조 list 를 사용했습니다. 해보진 않았지만 vector도 보나마나 시간 초과일껍니다.)