백준 1406. 에디터

문서 편집기를 구현하는 문제

vim이 이런식으로 구현되지 않았을까 싶다

1. 간단 설명

---

최대 600,000글자 까지 기록할 수 있는 에디터를 구현한다

커서를 이동하여 해당 위치에서 문자를 삭제하거나 추가할 수 있음

2. 문제 분석

---

1. 배열과 int cursor를 이용하는 방법

a
600000
L 
P a
L
P a
L 
P a
...

최대 600,000글자이므로 다음 같은 예시가 주어진다면

문자 하나를 맨 앞에 넣고, 모든 원소들을 뒤로 미루어야하기 때문에

최악의 경우 250000!의 시간 복잡도가 발생함

실패!

2. 연결리스트와 반복자를 이용한 구현

• 추가, 삭제할 때 엄청난 지연이 발생하는 것을 확인했으니, 이를 보완하기 위해 연결리스트 자료구조 사용
• STL List를 이용해 구현하고, cursor를 iterator를 이용해 구현

알고리즘

1. 문자열 S를 입력받아, 이를 char형 리스트에 넣는다
2. 반복자 커서를 생성 후, 마지막 위치로 할당한다. (명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치)
3. M을 입력받고, M개의 명령어들을 입력받는다
	3-1. L인 경우, 이동할 수 있다면 반복자를 앞으로 이동
	3-2. D인 경우, 이동할 수 있다면 반복자를 앞으로 뒤로 이동
	3-3. B인 경우, 커서의 왼쪽의 문자를 삭제해야하므로, 반복자를 앞으로 이동 후 삭제한다. 이후 뒤의 원소와 연결해준다
	3-4. P인 경우, 현재 반복자의 위치에 원소를 추가한다
4. 명령을 모두 수행했다면, 연결리스트의 원소를 처음부터 끝까지 출력하고 종료

소스코드

#include <iostream>
#include <list>

using namespace std;

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);

	int M;
	string s = "";

	cin >> s;

	list<char> li(s.begin(), s.end()); // 이렇게 생성 가능

	list<char>::iterator cursor;
	cursor = li.end();

	cin >> M;

	while (M--) {
		char cmd, c; cin >> cmd;

		switch (cmd)
		{
		case 'L':
			if (cursor != li.begin())
				cursor--;
			break;
		case 'D':
			if (cursor != li.end())
				cursor++;
			break;
		case 'B':
			if (cursor != li.begin()) {
				cursor--;
				cursor = li.erase(cursor); // 삭제 하고 iterator를 반환하는듯함
			}
			break;
		case 'P':
			cin >> c;
			li.insert(cursor, c); // iter 위치에 삽입
			break;
		}
	}

	for (cursor = li.begin(); cursor != li.end(); cursor++) {
		cout << *cursor;
	}

	return 0;
}

• list 생성자로 begin, end를 사용하는법 학습
• std::list::erase()는 삭제한 원소의 다음 원소를 가리키는 이터레이터를 리턴해준다는 것을 학습

3. 스택을 이용한 구현

• 두개의 스택을 운용함
• 따로 커서는 존재하지 않음
• 가상의 커서를 기준으로 왼쪽의 내용을 저장하는 스택과, 오른쪽의 내용을 저장하는 스택
• 책의 책장을 넘기는 것과 유사하게 생각하면 쉬움
• 오른쪽 내용의 스택은 거꾸로 쌓이는것에 주의할 것

알고리즘

1. 왼쪽 문자들을 저장할 스택과, 오른쪽 문자들을 저장하는 스택을 생성
2. 문자열 S를 입력받아, 왼쪽 스택에 모두 집어넣는다(커서가 문장 맨 뒤에 위치하므로)
3. M을 입력받고, M개의 명령어들을 입력받는다
	3-1. L인 경우, 왼쪽의 스택의 TOP을 빼서, 오른쪽 스택에 넣는다
	3-2. D인 경우, 오른쪽의 스택의 TOP을 빼서, 왼쪽 스택에 넣는다
	3-3. B인 경우, 왼쪽 스택에서 POP 한다 
	3-4. P인 경우, 왼쪽 스택에 PUSH 한다
4. 명령을 모두 수행했다면, 순서대로 출력해야하므로, 왼쪽 스택의 내용을 오른쪽 스택에 모두 집어넣는다
	- 현재 모든 원소가 역순임
5. 이후 오른쪽 스택의 내용을 TOP부터 모두 출력한다

소스코드

#include <iostream>
#include <stack>

using namespace std;

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);

	string str;  cin >> str;

	stack<char> left;
	stack<char> right;

	for (char ch : str) {
		left.push(ch);
	}

	int M; cin >> M;
	while (M--) {
		char cmd, c; cin >> cmd;
		switch (cmd)
		{
		case 'L':
			if (!left.empty()) {
				right.push(left.top());
				left.pop();
			}
			break;
		case 'D':
			if (!right.empty()) {
				left.push(right.top());
				right.pop();
			}
			break;
		case 'B':
			if (!left.empty()) {
				left.pop();
			}
			break;
		case 'P':
			cin >> c;
			left.push(c);
			break;
		default:
			break;
		}
	}

	while (!left.empty()) {
		right.push(left.top());
		left.pop();
	}

	while (!right.empty()) {
		cout << right.top();
		right.pop();
	}

	return 0;
}

• 이런 아이디어는 어떻게 떠올리는지 참 신기하다