1406 에디터

https://www.acmicpc.net/problem/1406

에디터를 구현하는 문제이다. 배열로 구현하면 삽입이나 삭제 연산이 O(N)이 걸리므로 스택이나 연결리스트를 이용해서 O(1)만에 삽입과 삭제가 가능하게 한다. 스택으로 구현시 커서를 기준으로 왼쪽, 오른쪽 두 개의 스택을 두고 구현한다.

스택 이용

#include <cstdio>
#include <stack>
using namespace std;
 
int main()
{
    stack<char> l,r;
    char c,a;
    while((c=getchar())!='\n') l.push(c);
    int n;
    scanf("%d",&n);
    while(n--)
    {
        scanf(" %c",&c);
        if(c=='L' && !l.empty()) r.push(l.top()),l.pop();
        else if(c=='D' && !r.empty()) l.push(r.top()),r.pop();
        else if(c=='B' && !l.empty()) l.pop();
        else if(c=='P') scanf(" %c",&a),l.push(a);
    }
    while(!l.empty()) r.push(l.top()),l.pop();
    while(!r.empty()) printf("%c",r.top()),r.pop();
    return 0;
}

연결리스트 이용

#include <cstdio>
#include <list>
using namespace std;
 
int main()
{
    list<char> l;
    char c,a;
    while((c=getchar())!='\n') l.push_back(c);
    int n;
    scanf("%d",&n);
    auto it=l.end();
    while(n--)
    {
        scanf(" %c",&c);
        if(c=='L' && it!=l.begin()) it--;
        else if(c=='D' && it!=l.end()) it++;
        else if(c=='B' && it!=l.begin()) { auto temp=it; l.erase(--temp); }
        else if(c=='P') scanf(" %c",&a),l.insert(it,a);
    }
    for(it=l.begin();it!=l.end();it++)
        printf("%c",*it);
    return 0;
}