글 읽기 - 3111번 시간초과가 뜨는데 도무지 이해가 안됩니다.. ㅜ

muselism 6년 전 0

제가 생각한 알고리즘은 스택에 문자를 하나씩 넣어가며

비교 문자열과 비교를해서 같은 문자면 top의 값을 비교문자열의 길이만큼 감소시키면서

스택을 채우는 알고리즘입니다.

그리고 끝의 동일 문자열이 존재할경우에는 널문자를 삽입하여 처리하였습니다.

그런데 문제는 이 코드로 돌리면 시간초과가 나는데 도무지 어디서 시간초과가 나는것인지 모르겠습니다.

혹시 main함수의 첫 for문에서 시간초과가 나는것일까요?]

ㅜㅜ..

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

#define MAX_WORD	300001
#define MAX_PART	26

typedef struct _stack {
	int top;
	char* buffer;
}Stack;


char word[MAX_WORD];
char part[MAX_PART];
Stack* sct;

void clearEnter(char str[]) {
	int length = strlen(str);
	str[length - 1] = '\0';
}

Stack* init() {
	Stack* newStack = (Stack*)malloc(sizeof(Stack));
	newStack->buffer = (char*)malloc(MAX_WORD);
	newStack->top = 0;
	return newStack;
}

void push(int* idx) {
	int length = strlen(part);
	int flag = 0;

	sct->buffer[(sct->top)++] = word[(*idx)++];
	if (sct->top >= length) {		// 스택요소 >= part의길이면 비교시작
		for (int i = 0; i < length; i++) 
			if (sct->buffer[sct->top - i - 1] != part[length - i - 1]) 
				return;

		sct->top -= length;
		char* tmp = word + strlen(word) - length;
		if (!strcmp(tmp, part))
			tmp[0] = '\0';
		//free(tmp);
		
	}
}

int main() {
	fgets(part, MAX_PART, stdin);	
	fgets(word, MAX_WORD, stdin);
	sct = init();
	clearEnter(part);
	clearEnter(word);
	int idx = 0;
	
	for (int i = 0; i < strlen(word); i++)	
		push(&idx);
	for (int i = 0; i < sct->top; i++)
		printf("%c", sct->buffer[i]);

	free(sct);
}

WeissBlume 6년 전 0

for (int i = 0; i < strlen(word); i++)

여기서 i < strlen(word); 부분이 우선 문제입니다. 이렇게 하면 strlen(word) 가 word의 길이만큼 불리게 됩니다(루프 한 바퀴당 한 번).

muselism 6년 전 0

하.. 저부분이 유동적이라 어쩔수없이 넣엇는데 저부분도 문제였군요 ...ㅜㅜ 감사합니다. 수정해보겠습니다.

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

문제

문제

출처

ICPC

3111번 시간초과가 뜨는데 도무지 이해가 안됩니다.. ㅜ

muselism 6년 전 0

WeissBlume 6년 전 0

muselism 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말