글 읽기 - 시간 줄이는 방법좀 알려주세요

wjdgud0621 5년 전 0

자꾸 시간 초과가 떠요. 어떻게 하면 실행 시간을 줄일 수 있을까요?

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

char input[1000001] = "0";
char bombString[37] = "0";

void stringErase(char* a, int b) {
	for (int i = b; a[i] != '\0'; i++)
	{
		a[i] = a[i + 1];
	}
}

int main() {
	int dnis = 0;
	int no = 0;
	scanf("%s", input);
	scanf("%s", bombString);
	while (1) {
		for (int i = 0; input[i] != '\0'; i++)
		{
			no = 1;
			if (input[i] == bombString[0]) {
				dnis = 0;
				for (int j = 0; bombString[j] != '\0'; j++)
				{
					if (input[i + j] == bombString[j]) {
						dnis++;
					}
				}
				if (dnis == strlen(bombString)) {
					for (int j = 0; j < strlen(bombString); j++)
					{
						stringErase(input, i);
						no = 1;
					}
				}
			}
		}
		if (no) break;
	}
	printf("%s", input);
}

seico75 5년 전 1

폭탄을 찾은 후 지우는 부분이 한 문자씩 지웁니다. 한번 지울때 전체 문자열을 뒷에서부터 가져와 복사를 해서 이 부분만 O(N*M) 이 걸릴 것 같습니다.
이것을 한번 돌리거 처음부터 다시 폭탄이 전체 없을 때 까지 반복을 시간에서 한참 늘어날 것 같습니다.

1번은 M개(폭탄의 길이)를 한꺼번에 당기면 O(N) 이 되겠지만, 원본문자열이 아닌 다른 문자열에 작업을 하면 O(1)도 가능합니다.

2는 정말 처음부터 돌려야 하는지 잘 생각해보시면 좋을 것 같습니다.

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

문제

문제

출처

ICPC

시간 줄이는 방법좀 알려주세요

wjdgud0621 5년 전 0

seico75 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말