[1406번] 에디터

1406번: 에디터

 

www.acmicpc.net

이 문제는 단순히 문자열을 erase함수를 통해 지워나가면 지운 빈 공간을 채우기 위해 앞으로 한칸씩 당기는 과정을 거치는데 문자열이 많아지거나 명령어가 많아지면 시간초과가 발생한다.

일반적으로 2가지 방법으로 풀수 있다.

1. 연결리스트

연결리스트를 이용하는 것은 직접 구현을 하거나 list STL을 사용하면된다.

연결리스트를 사용하면 단순 탐색시간만 소요되기 때문에 시간 내에 처리할 수 있다.

list를 이용해서 erase할 때, 반복자를 리스트.end()로 줄 경우 end()는 마지막 원소의 다음을 가르키기 때문에 주의해야한다.

/*1406번 에디터 (solved by list)*/
#include <iostream>
#include <string>
#include <list>
using namespace std;
string input;
int n;
char command, add_alpha;
list<char>l;
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> input;
	cin >> n;
	for (int i = 0; i < input.size(); i++) l.push_back(input[i]);
	list<char>::iterator cursor = l.end(), print_cursor;
	for (int i = 0; i < n; i++) {
		cin >> command;
		if (command == 'p') {
			cin >> add_alpha;
			l.insert(cursor, add_alpha);
		}
		else if (command == 'l') {
			if (cursor != l.begin()) cursor--;
		}
		else if (command == 'd') {
			if (cursor != l.end()) cursor++;
		}
		else if (command == 'b') {
			list<char>::iterator erase_cursor = cursor;
			if (cursor != l.begin()) l.erase(--erase_cursor);
		}
	}
	for (print_cursor = l.begin(); print_cursor != l.end(); print_cursor++) cout << *print_cursor;
}

 

2. 스택 이용

스택을 이용할 땐 스택 2개를 이용해서 스택 원소를 옮기는 것으로 커서를 표현할 수 있다.

 

"abcd"란 문자열에서 'L' 명령어를 2번 하게되면 아래와 같이 된다.

 

 

이런 식으로 두개의 스택을 이용해서 명령을 처리한다.

주의 할 점은 우측 스택은 순서가 뒤집어져 있다는 것을 신경써서 출력하면 된다.

/*1406번 에디터 (solved by stack)*/
#include<iostream>
#include<string>
#include<stack>
using namespace std;
stack<char>L, R, output;
int N;
string input;
char command, add_alpha;
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> input;
	for (int i = 0; i < input.size(); i++) L.push(input[i]);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> command;
		if (command == 'P') {
			cin >> add_alpha;
			L.push(add_alpha);
		}
		else if (command == 'L') {
			if (!L.empty()) {
				R.push(L.top());
				L.pop();
			}
		}
		else if (command == 'D') {
			if (!R.empty()) {
				L.push(R.top());
				R.pop();
			}
		}
		else if (command == 'B') {
			if (!L.empty()) {
				L.pop();
			}
		}
	}
	//좌측 스택 뒤집기
	while (!L.empty()) {
		output.push(L.top());
		L.pop();
	}
	//좌측 스택 출력
	while (!output.empty()) {
		cout << output.top();
		output.pop();
	}
	//우측 스택 출력
	while (!R.empty()) {
		cout << R.top();
		R.pop();
	}
}