BOJ - 에디터(1406)

이중 링크드 리스트(Double Linked List)이용하여 해결할 수 있는 문제입니다. 각 노드를 ‘커서’가 가리키고 있는 위치라고 한다면, 노드 안에 데이터는 ‘커서’ 바로 뒤의 문자입니다. 예를 들어서 문자열 ‘ABC’가 있으면 첫 번째 노드는 맨 앞 ‘커서’이고 가지고 있는 데이터는 ‘A’입니다. 즉, 각 노드는 ‘첫 번째 커서[A]’, ‘두 번째 커서[B]’, ‘세 번째 커서[C]’ 를 의미합니다. 그런데 ‘커서’가 문자열의 맨 뒤에도 위치할 수 있기 때문에 임의의 노드를 하나 더 추가해야 합니다.

구조체 배열

struct Node {
	Node* next;
	Node* prev;
	char data;
} nr[600005];
int nidx = 0;
Node* allocNode(char data) {
	Node* nn = &nr[nidx++];
	nn->data = data;
	return nn;
}

이중 링크드 리스트

Node* head = nullptr;
Node* tail = nullptr;

void add(char data) {
	Node* nn = allocNode(data);

	if (head == nullptr) {
		head = nn;
		tail = nn;
	} else {
		tail->next = nn;
		nn->prev = tail;
		tail = nn;
	}
}

편집기 기능

Node* pointer = nullptr;
void addAtPointer(char data) {
	Node* nn = allocNode(data);
	
	if (pointer == head) {
		nn->next = pointer;
		pointer->prev = nn;

		head = nn;
	} else {
		nn->next = pointer;
		nn->prev = pointer->prev;
		pointer->prev->next = nn;
		pointer->prev = nn;
	}
}
void del() {
	if (pointer == head) {
		return;
	}
	if (pointer->prev == head) {
		head = pointer;
		pointer->prev = nullptr;
	} else {
		pointer->prev->prev->next = pointer;
		pointer->prev = pointer->prev->prev;
	}
}

void left() {
	if (pointer != head) {
		pointer = pointer->prev;
	}
}

void right() {
	if (pointer != tail) {
		pointer = pointer->next;
	}
}

메인 함수

int main() {

	// 문자열 입력
	scanf("%s", str);
	getchar();

	// 문자열 링크드 리스트에 추가
	int strIdx = 0;
	while (str[strIdx] != '\0') {
		add(str[strIdx]);
		strIdx++;
	}

	// 맨 뒤에 커서 추가
	add('-');

	// 포인터 위치 초기화
	pointer = tail;

	int N;
	scanf("%d", &N);
	getchar();

	while (N--) {
		char key;
		scanf("%c", &key);
		getchar();
		if (key == 'P') {
			char nc;
			scanf("%c", &nc);
			getchar();
			addAtPointer(nc);
		} else if (key == 'L') {
			left();
		} else if (key == 'D') {
			right();
		} else if (key == 'B') {
			del();
		}
	}

	Node* cur = head;
	while (cur->data != '-') {
		printf("%c", cur->data);
		cur = cur->next;
	}
}