글 읽기 - 문자열 폭발 질문입니다. (정답있습니다.)

tjdgns9246 7년 전 0

일단 제 소스는 문자열을 하나씩 비교한 후에,

문자가 폭발문자열에 들어가있으면 STACK에 쌓습니다. 그 뒤, 만약 폭발문자열의 마지막 문자가 스택에 들어오면

폭발문자열이 스택에 존재하게 되는지 확인합니다. (존재하게 되면 스택에서 지웁니다.)

그리고 그 다음 문자가 폭발문자열에 포함되있지 않으면 스택에 쌓인 것들을 출력합니다.

그런데 이것의 메모리는 2296kb를 차지하고, 처리속도가 80ms로 매우 느리게 나타나던데...

어떻게 하면 조금 더 빠르게 코딩을 할 수 있을까요?

고수님들의 조언이 필요합니다ㅠ 감사합니다.

#include <stdio.h>
#include <string.h>
 
int main()
{
	int i, j, k, empty = 0, top = -1, pattern_length;
	char input[1000000], stack[500000], bomb[36];
	scanf("%s%s", input, bomb);
	pattern_length = strlen(bomb);
	
	for(i = 0; input[i] != '\0'; i++)
	{
		if(!strchr(bomb, input[i]))
		{
			for(j = 0; j <= top; j++)
				empty = printf("%c", stack[j]);
			top = -1;
			
			empty = printf("%c", input[i]);
		}
		else
		{
			stack[++top] = input[i];
            
            // found last character at the top of the stack
            if(stack[top] == bomb[pattern_length - 1])
            {
            	for(j = top, k = pattern_length - 1; k > -1; j--, k--)
            		if(stack[j] != bomb[k])
            			break;
            			
            	// found pattern in the stack
            	if(k == -1)
            		for(j = pattern_length - 1; j > -1; j--)
            			stack[top--] = 0;
            }
        }
    }
    for(j = 0; j <= top; j++)
    	empty = printf("%c", stack[j]);
    	
    if(!empty)
    	printf("FRULA");
}

portableangel 7년 전 0

최대 문자 100만개를 출력해야 해서 출력 시간이 깁니다.

마지막 남은 문자들을 모두 모아 문자열 하나로 만들어 한 번에 출력해보시면 실행시간이 제법 줄어들거예요

tjdgns9246 7년 전 0

@portableangel 님,

그렇게 되면 메모리를 엄청 잡아먹지 않나요?

메모리와 실행시간을 둘 다 효율적으로 사용할 수 있는 방법은 없나요?

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

문제

문제

출처

ICPC

문자열 폭발 질문입니다. (정답있습니다.)

tjdgns9246 7년 전 0

portableangel 7년 전 0

tjdgns9246 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말