[C++] 1406번 : 에디터

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

1406번: 에디터

풀이

vector 또는 단순 배열을 이용하여 풀어볼 수 있겠구나 라고 생각할 수 있다.

그러나 수상하게도 문제에서 주어진 시간 제한이 0.3초이다.

즉 각 명령어를 수행할 때 O(n)이 아닌 O(1)인 코드를 기술해야한다.(즉 각 명령어를 수행할 때마다 문자열 전체를 봐야하는 것은 안된다! -> vector과 배열을 사용할 시 O(mn)이 되므로 불가하다.)

그에 딱 맞는 자료구조로 Linked List가 있다. 위치만 주어진다면 삽입과 삭제를 O(1)에 수행할 수 있다!

 

코드

 

#include <bits/stdc++.h>
using namespace std;
//배열로 구현하는 야매 연결리스트
const int MX = 1000005;
char dat[MX];
int pre[MX];
int nxt[MX];
int unused = 1;

void insert(int addr, char num) {
	dat[unused] = num;
	pre[unused] = addr;
	nxt[unused] = nxt[addr];
	if(nxt[addr] != -1)pre[nxt[addr]] = unused;
	nxt[addr] = unused;
	unused++;
}

void erase(int addr) {
	if (nxt[addr] != -1)pre[nxt[addr]] = pre[addr];
	nxt[pre[addr]] = nxt[addr];
}

void traversal() {
	int cur = 0;
	while (nxt[cur] != -1) {
		cout << dat[cur];
		cur++;
	}
}


int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	fill(pre, pre + MX, -1);
	fill(nxt, nxt + MX, -1);
	string s;
	cin >> s;
	int cursor = 0;
	for (auto c : s) {
		insert(cursor, c);
		cursor++;
	}

	int M;
	cin >> M;
	while (M--) {
		char command;
		cin >> command;
		if (command == 'L') {
			if (pre[cursor] != -1)cursor = pre[cursor];
		}
		if (command == 'D') {
			if (nxt[cursor] != -1)cursor = nxt[cursor];
		}
		if (command == 'B') {
			if (pre[cursor] != -1) {
				erase(cursor);
				cursor = pre[cursor];
			}
		}
		if (command == 'P') {
			char ch;
			cin >> ch;
			insert(cursor, ch);
			cursor = nxt[cursor];
		}
	}
	traversal();
}

#include <bits/stdc++.h>
using namespace std;
//STL LLS
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin >> s;
	list<char> l;
	for (auto c : s) l.push_back(c);
	auto cursor = l.end(); // list<char>::iterator cursor = l.end();
	int M;
	cin >> M;
	while (M--) {
		char command;
		cin >> command;
		if (command == 'L')
		{
			if (cursor != l.begin()) cursor--;
		}
		if (command == 'D')
		{
			if (cursor != l.end()) cursor++;
		}
		if (command == 'B') {
			if (cursor != l.begin()) {
				cursor--;
				cursor = l.erase(cursor);
			}	
		}
		if (command == 'P') {
			char ch;
			cin >> ch;
			l.insert(cursor,ch);
		}
	}
	for (auto a = l.begin(); a != l.end(); a++)
		cout << *a;

}

+)이 문제는 Stack으로도 풀 수 있는 것 같았다.