글 읽기 - 시간초과에 대한 조언 부탁드립니다.

gbkim542 6년 전 0

실행시 결과는 잘 나오는데 시간초과라고 나옵니다. 원인이 무엇인지 조언 부탁드립니다.

#pragma warning(disable: 4996)

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

//스택 관련 구조체, 함수 
typedef char Data;

typedef struct _node
{
	Data data;
	struct _node * next;
} Node;

typedef struct _listStack
{
	Node * head;
} ListStack;

typedef ListStack Stack;

void StackInit(Stack * pstack)
{
	pstack->head = NULL;
}

int SIsEmpty(Stack * pstack)
{
	if (pstack->head == NULL)
		return 1;
	else
		return 0;
}

//데이터 삽입
void SPush(Stack * pstack, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));

	newNode->data = data;
	newNode->next = pstack->head;

	pstack->head = newNode;
}

//마지막에 들어간 데이터 반환 후 삭제
Data SPop(Stack * pstack)
{
	Data rdata;
	Node * rnode;

	rdata = pstack->head->data;
	rnode = pstack->head;

	pstack->head = pstack->head->next;
	free(rnode);

	return rdata;
}

//마지막에 들어간 데이터 반환, 삭제x
Data SPeek(Stack * pstack)
{
	return pstack->head->data;
}

//뒤에서 부터 검열, 앞에서 부터 검열하는 함수
int BackCensorship(Stack * dst_stack, Stack * src_stack, char word[], int w_length);
int FrontCensorship(Stack * dst_stack, Stack * src_stack, char word[], int w_length);

int main(void)
{
	int I, J = 0;
	int s_length, w_length;
	int del;
	int state = 0;
	int ExistWordFlag = 0; //string 내에 단어 존재하면 1
	int CNT = 0;           //단어를 검열한 회수
	char Word[25];
	char String[300000];

	Stack f_stack;
	Stack b_stack;
	StackInit(&f_stack);
	StackInit(&b_stack);

	scanf("%s", &Word);
	scanf("%s", &String);

	s_length = strlen(String);
	w_length = strlen(Word);

	//string을 stack에 옮겨담으며 ExistWordFlag를 결정
	for (I = 0; I < s_length; I++)
	{
		SPush(&f_stack, String[I]);

		if (J != w_length)
		{
			if (Word[J] == SPeek(&f_stack))
			{
				J++;
				if (J == w_length)
				{
					ExistWordFlag = 1;
					CNT++;
					for (del = 0; del < w_length; del++)
						SPop(&f_stack);
				}
			}
			else
			{
				if (!J) //첫번째 문자부터 일치하지 않으면
				{
					continue;
				}
				else  //두번째 이상인 문자부터 일치하지 않으면 
				{
					for (del = 0; del < J; del++) //두번째 문자부터는 stack에서 삭제
					{
						SPop(&f_stack);
					}
					I -= J;
					J = 0;
				}
			}
		}
	}

	while (ExistWordFlag)
	{
		ExistWordFlag = state ? FrontCensorship(&f_stack, &b_stack, Word, w_length) : BackCensorship(&b_stack, &f_stack, Word, w_length);
		if (ExistWordFlag)
			CNT++;
		state = state ? 0 : 1;
	}

	if (!state)
	{
		while (!SIsEmpty(&f_stack))
		{
			SPush(&b_stack, SPop(&f_stack));
		}
	}

	J = s_length - CNT * w_length;//현재 string 길이
	
	for (I = 0; I < J; I++)//stack에 있는 문자를 순서대로 출력
	{
		printf("%c", SPop(&b_stack));
	}

	return 0;
}
//string의 뒤에서 부터 단어 검색 후, 존재하면 삭제하고 1반환, 존재하지 않으면 0반환  
int BackCensorship(Stack * dst_stack, Stack * src_stack, char word[], int w_length)
{
	int i, j = w_length - 1;
	int del;
	int cnt = 0;
	int ExistWordFlag = 0;
	char string[299997];

	while (!SIsEmpty(src_stack))
	{
		string[cnt++] = SPop(src_stack);
	}

	for (i = 0; i < cnt; i++)
	{
		SPush(dst_stack, string[i]);

		if (j != -1)
		{
			if (word[j] == SPeek(dst_stack))
			{
				j--;
				if (j == -1)
				{
					ExistWordFlag = 1;
					for (del = 0; del < w_length; del++)
						SPop(dst_stack);
				}
			}
			else
			{
				if (j == w_length - 1)
				{
					continue;
				}
				else  
				{
					for (del = 0; del < w_length - 1 - j; del++)
					{
						SPop(dst_stack);
					}
					i -= w_length - 1 - j;
					j = w_length - 1;
				}
			}
		}
	}

	return ExistWordFlag;
}
//string의 앞에서 부터 단어 검색 후, 존재하면 삭제하고 1반환, 존재하지 않으면 0반환 
int FrontCensorship(Stack * dst_stack, Stack * src_stack, char word[], int w_length)
{
	int i, j = 0;
	int cnt = 0;
	int del;
	int ExistWordFlag = 0;
	char string[299994];

	while (!SIsEmpty(src_stack))
	{
		string[cnt++] = SPop(src_stack);
	}

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

		SPush(dst_stack, string[i]);

		if (j != w_length)
		{
			if (word[j] == SPeek(dst_stack))
			{
				j++;
				if (j == w_length)
				{
					ExistWordFlag = 1;
					for (del = 0; del < w_length; del++)
						SPop(dst_stack);
				}
			}
			else
			{
				if (!j)
				{
					continue;
				}
				else  
				{
					for (del = 0; del < j; del++)
					{
						SPop(dst_stack);
					}
					i -= j;
					j = 0;
				}
			}
		}
	}

	return ExistWordFlag;
}

bupjae 6년 전 1

이 프로그램은 지워야 할 문자열을 지운 후에 스택 1에 남아있는 모든 데이터를 스택 2로 옮기고 있습니다.

이래서야 스택을 사용하지 않고 짠 프로그램과 시간복잡도가 같아져서 스택을 사용한 의미가 없어집니다.

gbkim542 6년 전 0

감사합니다. 많은 도움이 됐습니다.

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

문제

문제

출처

ICPC

시간초과에 대한 조언 부탁드립니다.

gbkim542 6년 전 0

bupjae 6년 전 1

gbkim542 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말