백준 5379번 키로거

내 코드

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct node
{
	char data;
	struct node* prev;
	struct node* next;
}Node;//양방향 연결리스트

void Insert(Node* cur, char data)
{
	Node* temp = cur->next;//A B사이에 C를 삽입한다 가정
    //A의 next를 C로 하고(1) C의 양쪽에 A,B를 연결해야 하고(2),(3), B의 prev를 C로 해야한다.(4)
	cur->next = malloc(sizeof(Node));//cur는 A, A의 next는 C/(1)
	cur->next->data = data;//C에 데이터를 삽입
	cur->next->next = temp;//C의 next는 B/(3)
	if(temp != NULL) temp->prev = cur->next;//B가 NULL이 아니면 B의 이전애 C를 연결/(4)
	cur->next->prev = cur;//C의 이전은 A/(2)
}

Node* Delete(Node* cur)
{
	Node* temp_next = cur->next;
	Node* temp_prev = cur->prev;
	temp_prev->next = temp_next;
	if(temp_next != NULL) temp_next->prev = temp_prev;//삭제되는 데이터의 next가 NULL일 때는 예외처리, NULL이 아니면 그 노드의 prev는 'cur의 prev'이다.
	free(cur);
	return temp_prev;
}

int main()
{
	int T;
	int i, j, length;
	char array[1000001];

	scanf("%d", &T);

	for (j = 0; j < T; j++)
	{
		Node* head = malloc(sizeof(Node));
		Node* cur = head;
		cur->prev = NULL;
		cur->next = NULL;//헤드만들고 처음에 커서가 헤드를 가리키게 함


		scanf("%s", array);

		length = strlen(array);

		for (i = 0; i < length; i++)
		{

			if (array[i] == '-')
			{
				if (cur == head) continue;//예외처리 해주어야함.
				else cur = Delete(cur);//당연히 한칸 땡겨줘야함
			}

			else if (array[i] == '<')
			{
				if (cur == head) continue;

				else
				{
					cur = cur->prev;
				}
			}

			else if (array[i] == '>')
			{
				if (cur->next == NULL) continue;

				else
				{
					cur = cur->next;
				}
			}

			else
			{
				Insert(cur, array[i]);
				cur = cur->next;//Insert함수 안에 넣어도 좋다. cur는 한칸이동해야 한다.
			}
		}

		cur = head;

		while (cur->next != NULL)
		{
			cur = cur->next;
			printf("%c", cur->data);
		}

		printf("\n");
	}

	return 0;
}

다른 사람의 코드

https://www.acmicpc.net/user/4rchive_7 님의 코드

https://www.acmicpc.net/source/10105870

#include <stdio.h>
#include <malloc.h>

#define _ASZ 1000010

typedef struct node{
	struct node *prev, *next;
	char w;
}LNODE;

LNODE *start, *end, *cursor;
LNODE node[_ASZ];
int index = 0;
void init(){
	LNODE *s = (LNODE *)malloc(sizeof(LNODE));
	LNODE *e = (LNODE *)malloc(sizeof(LNODE));

	s->w = 1;
	e->w = 2;
	s->prev = NULL;
	e->next = NULL;
	s->next = e;
	e->prev = s;

	start = s;
	end = e;
}

void rmAll(){
	LNODE *prev = start, *next = start;
	while (next != NULL){
		prev = next;
		next = next->next;
		free(prev);
	}
}

void removeList(){
	LNODE *prev = cursor->prev, *next = cursor->next;
	prev->next = next;
	next->prev = prev;
	cursor = prev;
}

LNODE *createNode(char c){
//	LNODE *newNode = (LNODE *)malloc(sizeof(LNODE));
	LNODE *newNode = &node[index++];
	newNode->prev = NULL;
	newNode->next = NULL;
	newNode->w = c;

	return newNode;
}

void appendList(LNODE *newNode){
	LNODE *next = cursor->next;
	cursor->next = newNode;
	newNode->prev = cursor;
	next->prev = newNode;
	newNode->next = next;
	cursor = newNode;
}


int main(){
	int N;
	scanf("%d", &N);
	char comm[1000001], c, *s;
	init();
	while (N--){
		start->next = end;
		end->prev = start;
		cursor = start;
		index = 0;
		scanf("%s", comm);
		s = comm;
		while(c = *s++){
			if (c == '<'){
				if (cursor->prev != NULL) cursor = cursor->prev;
			}
			else if (c == '>'){
				if (cursor->next->w != 2) cursor = cursor->next;
			}
			else if (c == '-'){
				if (cursor->prev != NULL) removeList();
			}
			else{
				appendList(createNode(c));
			}
		}
		for (LNODE *p = start->next; p->w != 2; p = p->next)
			printf("%c", p->w);
		printf("\n");
		//rmAll();
	}
	return 0;
}

노드 자료형으로 100만칸짜리 배열을 만드는 것을 보아 malloc을 여러번 하는 것보다 배열을 만들어 이 주소들을 각각의 노드로 활용한 것을 알 수 있다.

나와 이 사람의 시간차가 여기서 났음을 알 수 있다.

다음부터 풀어볼 때는 시간 절약을 위해 이런 방법을 활용해봐야겠다.

[정리]

1. 연결리스트를 만들 때 malloc하는 시간을 좀더 줄이는 방법 (Node의 최대 개수를 알 때, 활용할 수 있는 방법)

malloc을 여러번 하는 대신 배열로 한번에 Node를 여러개 만드는 방식

2. 야매 연결리스트 (그래프에서 사용)

노드의 개수가 충분히 적을 때
이차원 배열을 만들어 연결리스트로 구현한 그래프처럼 활용하는 방식