백준 C++ 1406번) 에디터

 

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

 

https://blog.encrypted.gg/932?category=773649  님의 강의를 보고 문제를 풀어봤습니다. 물론 제 개인적으로 만든 연결리스트 코드도 있습니다.

1406번: 에디터

[실전 알고리즘] 0x04강 - 연결 리스트

 

강의를 보고 쓴 코드

#pragma warning(disable:4996)
#include<iostream>
#include<string>

using namespace std;
#define MX 1000005

char dx[MX];
int pre[MX];
int nxt[MX];
int unused = 1;
void Insert(int cursur, char c) {
	dx[unused] = c;
	pre[unused] = cursur;
	nxt[unused] = nxt[cursur];
	if (nxt[cursur] != -1) pre[nxt[cursur]] = unused;
	nxt[cursur] = unused;
	unused++;
}

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	string s;
	int cursur = 0;
	fill(pre, pre + MX, -1);
	fill(nxt, nxt + MX, -1);
	cin >> s;
	for (auto a : s) {
		Insert(cursur, a);
		cursur++;
	}
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		char op;
		cin >> op;
		switch (op) {
		case 'L':
			if (pre[cursur] != -1) cursur = pre[cursur];
			break;
		case 'D':
			if (nxt[cursur] != -1) cursur = nxt[cursur];
			break;
		case 'B':
			if (pre[cursur] != -1) {
				Delete(cursur);
				cursur = pre[cursur];
			}
			break;
		case 'P':
			char str;
			cin >> str;
			Insert(cursur, str);
			cursur = nxt[cursur];
			break;
		}
	}
	int i = 0;
	while (nxt[i] != -1) {
		printf("%c", dx[nxt[i]]);
		i = nxt[i];
	}
}

 

제가 직접 만든 코드( 백준에서 에러가 나긴 하는데 뭐가 문제인지는 잘 모르겠습니다.. 아시는 분 있으시면 댓글 부탁드리겠습니다. )

#include<iostream>
#include<string>

using namespace std;
typedef struct Node {
	Node(char c) : c(c) {}
	char c;
	Node* Next = nullptr;
	Node* Prev = nullptr;
};

Node* Head = nullptr;

void MoveLeft(Node* Cursur) {
	if (Cursur->Prev != nullptr) {
		Cursur->Next = Cursur->Prev;
		Cursur->Prev = Cursur->Prev->Prev;
	}
}

void MoveRight(Node* Cursur) {
	if (Cursur->Next != nullptr) {
		Cursur->Prev = Cursur->Next;
		Cursur->Next = Cursur->Next->Next;
	}
}

void Insert(Node* Cursur, char c) {
	Node* tmp = new Node(c);
	tmp->Next = Cursur->Next;
	tmp->Prev = Cursur->Prev;
	if (Cursur->Next != nullptr)
		Cursur->Next->Prev = tmp;
	if (Cursur->Prev != nullptr)
		Cursur->Prev->Next = tmp;
	Cursur->Prev = tmp;
	if (tmp->Prev == nullptr)
		Head = tmp;
}

void Delete(Node* Cursur) {
	Node* tmp = Cursur->Prev;
	if (tmp != nullptr) {
		if (tmp->Prev != nullptr)
			tmp->Prev->Next = Cursur->Next;
		if (tmp->Next != nullptr)
			tmp->Next->Prev = Cursur->Prev->Prev;
		Cursur->Prev = Cursur->Prev->Prev;
		//delete tmp;
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	string s;
	Node* Cursur = new Node(0);		
	cin >> s;
	for (auto a : s) {
		Node* tmp = new Node(a);
		tmp->Next = Cursur;
		tmp->Prev = Cursur->Prev;
		if (Head == nullptr) {
			Head = tmp;
		}
		else {
			Cursur->Prev->Next = tmp;
		}
		Cursur->Prev = tmp;
	}
	Cursur->Prev->Next = nullptr;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		char op;
		cin >> op;
		switch (op) {
		case 'L':
			MoveLeft(Cursur);
			break;
		case 'D':
			MoveRight(Cursur);
			break;
		case 'B':
			Delete(Cursur);
			break;
		case 'P':
			char str;
			cin >> str;
			Insert(Cursur, str);
			break;
		}
	}
	if (Cursur->Next == nullptr && Cursur->Prev == nullptr)
		printf("");
	else {
		while (Head != nullptr) {
			printf("%c", Head->c);
			Head = Head->Next;
		}
	}
}