글 읽기 - 1406 에디터 시간초과 질문입니다.

chc0331 5년 전 0

C로 링크드리스트 직접 구현해서 소스 짜봤는데 시간초과 원인이 뭔지 궁금해서 질문드립니다.

초기 문자열 문자 갯수 +1 만큼 노드만들어서 링크드리스트로 연결했고 삽입 삭제 할때 next before 포인터로 연결해주고 빼줬습니다.

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

char str[100005];
char order[10];
int N;

typedef struct node
{
	struct node*next; //다음노드연결 포인터
	struct node*before;//이전노드 연결 포인터
	char ch;
}Node;

int main(void)
{
	int i;
	Node *head=(Node*)malloc(sizeof(Node));
	head->ch=0;
	Node *tail;
	head->next=head;head->before=head;
	tail=head;
	Node * cursor;
	Node *ptr;
	scanf("%s",str);

	for(i=0;i<100000;i++)
	{
		if(str[i]=='\0')
			break;
		Node *n=(Node*)malloc(sizeof(Node));
		n->ch=str[i];
		n->next=head;
		if(i==0)
			head->next=n;
		head->before=n;
		n->before=tail;
		tail->next=n;
		tail=n;
	}//초기 문자열 문자 갯수+1 만큼 노드 만들어서 링크드리스트로 연결
	cursor=tail;

	scanf("%d",&N);
	fflush(stdin);
	for(i=1;i<=N;i++)
	{
		fgets(order,10,stdin);
		fflush(stdin);
		if(order[0]=='L')
		{
			if(cursor!=head)
				cursor=cursor->before;
		}
		else if(order[0]=='D')
		{
			if(cursor!=tail)
				cursor=cursor->next;
		}
		else if(order[0]=='B')//삭제
		{
			if(cursor!=head)
			{
			(cursor->before)->next=cursor->next;
			(cursor->next)->before=cursor->before;
			if(cursor==tail)
			{
				tail=cursor->before;
			}
			cursor=cursor->before;
			}
		}
		else//삽입
		{
			Node *n=(Node *)malloc(sizeof(Node));
			n->ch=order[2];
			n->before=cursor;
			n->next=cursor->next;
			(cursor->next)->before=n;
			cursor->next=n;
			if(cursor==tail)
			{
				tail=n;
			}
			cursor=n;
		}
	}

	ptr=head->next;
	while(1)
	{
		printf("%c",ptr->ch);
		if(ptr==tail)
			break;
		ptr=ptr->next;
	}
	
	return 0;
}	

djm03178 5년 전 1

fflush(stdin); 은 표준이 아니며, 구버전 비주얼 스튜디오에서만 동작하던 기능입니다.

개행 문자 하나를 제거하고 싶다면 getchar(); 를 쓰면 되고, 48번째 줄에는 아예 필요하지 않습니다.

chc0331 5년 전 0

아 덕분에 해결했습니다. 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1406 에디터 시간초과 질문입니다.

chc0331 5년 전 0

djm03178 5년 전 1

chc0331 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말