04 연결리스트(2) - 백준 1406 에디터

#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, int num) {
	//insert(1,30)
	dat[unused] = num;
	pre[unused] = addr;
	nxt[unused] = nxt[addr];

	int next = nxt[addr];
	if (next != -1)
		pre[next] = unused;
	nxt[addr] = unused;
	unused++;



}

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

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

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	fill(pre, pre + MX, -1);
	fill(nxt, nxt + MX, -1);
	string init;
	cin >> init;
	int cursor = 0;
	for (auto c : init) {
		insert(cursor, c);
		cursor++;
	}
	int q;
	cin >> q;
	while (q--) {
		char op;
		cin >> op;
		if (op == 'P') {
			char add;
			cin >> add;
			insert(cursor, add);
			cursor = nxt[cursor];
		}
		else if (op == 'L') {
			if (pre[cursor] != -1) cursor = pre[cursor];
		}
		else if (op == 'D') {
			if (nxt[cursor] != -1) cursor = nxt[cursor];
		}
		else { // 'B'
			if (pre[cursor] != -1) {
				erase(cursor);
				cursor = pre[cursor];
			}
		}
	}
	traversal();
}

 

 

예제입력 1

abcd
3
P x
L
P y

 위 예시로 이해를 하고자 그림판에서 상황을 그려보았다.

 

부딪혔던 문제)

#include <bits/stdc++.h> 이 컴파일이 되지 않아

https://mirae-kim.tistory.com/20 를 참고하여

헤더파일을 경로에 넣어주었다.

 

 

출처:basic-algo-lecture/1406_2.cpp at master · encrypted-def/basic-algo-lecture · GitHub