[BOJ] 1406 - 에디터

Sierra·2022년 6월 29일

boj 공부노트 대학생 리스트 스택 자료구조 코딩공부

[BOJ] DataStructure

목록 보기

4/5

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

문제

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

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

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

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

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

입력

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

출력

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

예제 입출력

예제 입력 1

abcd
3
P x
L
P y

예제 출력 1

abcdyx

예제 입력 2

abc
9
L
L
L
L
L
P x
L
B
P y

예제 출력 2

yxabc

예제 입력 3

dmih
11
B
B
P x
L
B
B
B
P y
D
D
P z

예제 출력 3

yxz

Solution

두 가지 방법이 있다.

1. List를 활용하는 방법.

사실 C++로 문제를 풀 때 가변배열(vector)을 주로 사용했지 List를 써 본 건 처음이었다.

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string tmp; cin >> tmp;
    int M; cin >> M;
    list<char> lst(tmp.begin(), tmp.end());
    list<char>::iterator now = lst.end();
    while(M--){
        char tmp;
        cin >> tmp;
        if(tmp == 'L'){
            if(now != lst.begin()){
                now--;
            }
        } else if (tmp == 'D'){
            if(now != lst.end()){
                now++;
            }
        } else if (tmp == 'B'){
            if(now != lst.begin()){
                now = lst.erase(--now);
            }
        } else if (tmp == 'P'){
            char input;
            cin >> input;
            lst.insert(now, input);
        }
    }
    for(list<char>::iterator it = lst.begin(); it != lst.end(); it++){
        cout << *it;
    }
}

list와 iterator의 개념을 이해하면 쉽게 풀 수 있다.
iterator 란 반복자를 의미한다. JAVA든 C++이든 iterator가 존재한다.
iterator를 사용하면, 어떤 컨테이너(컬렉션)이든 순차적으로 쉽게 접근 할 수 있다.

자료구조 시간에 공부 해 보았겠지만, 어떤 구조든 간에 생성 원리가 다르기 때문에 무작정 인덱스 접근은 상황에 따라 권장되지 않는다.

Map을 사용한다고 생각 해 보자. 인덱스가 따로 정해 져 있지 않고 오직 Key와 Value로 값을 저장한다. 처음부터 끝 까지 순회해서 확인하려면 iterator의 도움이 필요하다.

사실 리스트는 인덱스로 접근하는 게 빠를 수도 있다. 크게 차이는 나지 않지만 iterator의 사용법을 잘 숙지 해 두는 게 좋다. 어떤 자료구조를 사용한 들 편리하게 사용 할 수 있으니까.

string tmp; cin >> tmp;
int M; cin >> M;
list<char> lst(tmp.begin(), tmp.end());
list<char>::iterator now = lst.end();

입력 받은 문자열을 list에 하나 하나 저장한다. (포인터의 힘이란...)
그리고 리스트의 마지막 원소를 바라보는 iterator 객체를 하나 생성한다.
iterator의 템플릿 형태는 반드시 잘 지정 해 주어야 한다. (귀찮으면 auto를 쓰면 그만이긴 하다.)

 while(M--){
    char tmp;
    cin >> tmp;
    if(tmp == 'L'){
        if(now != lst.begin()){
            now--;
        }
    } else if (tmp == 'D'){
        if(now != lst.end()){
            now++;
        }
    } else if (tmp == 'B'){
        if(now != lst.begin()){
            now = lst.erase(--now);
        }
    } else if (tmp == 'P'){
        char input;
        cin >> input;
        lst.insert(now, input);
	}
}
for(list<char>::iterator it = lst.begin(); it != lst.end(); it++){
    cout << *it;
}

그 다음은 간단하다. 명령에 따라 iterator를 이동 시켜 주자. 사실상 이게 커서 역할을 해 주니까.
B와 P 명령은 좀 신경써야 한다.
B명령에서는 자신의 왼쪽 데이터를 삭제시킨다는 개념, 즉 커서의 위치가 왼쪽으로 한칸 이동한 것과 같다. 그러므로 전위연산을 통해 현재 위치의 왼쪽 데이터를 삭제 후 iterator를 이동시켜준다.
P명령은 크게 어렵지 않다. 현재 iterator의 위치에서 데이터를 insert 하면 그만이니까.

전체 출력도 어렵지 않다. iterator를 이동시키며 쭉 출력시켜주자. 단, iterator에 저장되어 있는 건 해당 데이터의 메모리 주소다. 즉 포인터를 사용 할 때와 같이 포인터 연산자를 통해 실제 값을 출력 시켜 줘야 한다.

2. Stack을 활용하는 방법

이건 좀 신박하더라...

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string tmp; cin >> tmp;
    int M; cin >> M;
    stack<char> l;
    stack<char> r;
    for(int i = 0; i < tmp.length(); i++){
        l.push(tmp[i]);
    }
    while(M--){
        char cmd;
        cin >> cmd;
        if(cmd == 'L'){
            if(!l.empty()){
                r.push(l.top());
                l.pop();
            }
        } else if (cmd == 'D'){
            if(!r.empty()){
                l.push(r.top());
                r.pop();
            }
        } else if (cmd == 'B'){
            if (!l.empty()){
                l.pop();
            }
        } else if (cmd == 'P'){
            char input; cin >> input;
            l.push(input);
        }
    }
    while(!l.empty()){
        r.push(l.top());
        l.pop();
    }
    while(!r.empty()){
        cout << r.top();
        r.pop();
    }

}