1406: 에디터

• toc {:toc}

문제

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 ‘커서’라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

L	커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D	커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B	커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $	$라는 문자를 커서 왼쪽에 추가함

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

입력

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

출력

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

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

풀이

연결리스트 야매 구현방법 확실하게 익혀두기 ⇒ 3, 4번 더 구현해보기

야매 풀이법

// 연결리스트
#include <bits/stdc++.h>
 
using namespace std;
 
const int MX = 1000005;
char dat[MX];
int pre[MX], nxt[MX];
int unused = 1;
 
void insert(int addr, char data){
    dat[unused] = data;
    pre[unused] = addr;
    nxt[unused] = nxt[addr];
    if(nxt[addr] != -1) pre[nxt[addr]] = unused;
    nxt[addr] = unused;
    unused++;
}
 
void erase(int addr){
    nxt[pre[addr]] = nxt[addr];
    if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
}
 
void traverse(){
    int cur = nxt[0];
    while(cur != -1){
        cout << dat[cur];
        cur = nxt[cur];
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    fill(pre, pre+MX, -1);
    fill(nxt, nxt+MX, -1);
    string str;
    int N, M, cursor=0;
    char inp;
    cin >> str >> M;
    N = str.size();     // 문자열의 길이
    for(auto elem : str){       // 문자열의 문자를 연결리스트로 자료화
        insert(cursor, elem);
        cursor++;
    }
 
    for (int i = 0; i < M; i++)             // 조작키를 눌렀을 때
    {
        cin >> inp;
        switch (inp){
            case 'L':
                if(pre[cursor] != -1) cursor = pre[cursor];
                break;
            case 'D':
                if(nxt[cursor] != -1) cursor = nxt[cursor];
                break;
            case 'B':
                if(pre[cursor] != -1){          // 커서의 차이 dat일 때 pre일 때
                    erase(cursor);              // dat일 때로 하면 커서가 하나 더 이전으로 위치하게 됨
                    cursor = pre[cursor];
                }
                
                break;
            case 'P':
                char c1;
                cin >> c1;
                insert(cursor, c1);
                cursor = nxt[cursor];
                break;
        }
    
    }
    
    traverse();
 
    return 0;
}

STL List 사용

현재 문자열이 ABCD일 때

(1) A (2) B (3) C (4) D (5)

L.end() ⇒ 5번

L.begin() ⇒ 1번

L.erase()를 사용할 때는 앞쪽에 위치해야 지울 수 있음.

예를 들어 4번에 있어야 D를 지울 수 있음. 이후 오른쪽 문자 반환

3번 자리에서 C를 지웠을 경우 4번자리에 위치함.

L.insert()는 삽입 후 반환값이 원래 가르키는 문자를 가르킴

예를 들어 K를 2번에 삽입한 경우 3번 자리에 위치함.

(1) A (2) K (3) B (4) C (5) D (6)

// 연결리스트 stl list 사용
#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    list<char> L;
    string str;
    int M;
    cin >> str;
    for(auto elem : str) {
        L.push_back(elem);
    }
    auto cursor = L.end();
    cin >> M;
    char p;
    while(M--) {
        cin >> p;
        switch(p) {
            case 'L':
                if(cursor != L.begin()) cursor--;
                break;
            case 'D':
                if(cursor != L.end()) cursor++;
                break;
            case 'B':
                if(cursor != L.begin()) {
                    cursor--;
                    cursor = L.erase(cursor);
                }
                break;
            case 'P':
                char inp;
                cin >> inp;
                L.insert(cursor, inp);
                break;
        }
        
    }
 
    for(auto elem : L)
        cout << elem;
 
    return 0;
}