글 읽기 - 9935번 시간초과ㅠㅠㅠㅠ

rindo98 5년 전 0

처음에는 string 에서 find랑 erase를 써서 풀었는데 그것도 시간초과가 되더라구요

그래서 cstring으로 방향을 바꿨는데 또 시간초과 ㅎㅅㅎ

어떻게 고쳐야 될까요..

#include<iostream>
#include<cstring>

using namespace std;

int main() {
	int i;
	char*str = (char*)calloc(100100, sizeof(char));
	char*boom = (char*)calloc(40, sizeof(char));
	char*ans = (char*)calloc(100100, sizeof(char));
	cin.getline(str, 100100);
	cin.getline(boom, 40);
	int copy = 0;
	int cmp = strlen(boom);
	for (i = 0; i <= strlen(str); i++) {
		if (copy>=cmp&&strncmp(ans + copy - cmp, boom, cmp)==0)
			copy = copy - cmp;
		ans[copy] = str[i];
		copy++;
	}
	if (copy == 0)
		cout << "FRULA" << endl;
	else {
		ans[copy] = '\0';
		cout << ans << endl;
	}
	return 0;
}

djm03178 5년 전 0

strlen은 문자열의 처음부터 끝까지 탐색하며 널 문자가 나타나는 곳을 찾습니다.

그래서 길이가 N인 문자열을 저렇게 반복문을 돌리면 O(N^2) 시간이 걸립니다.

문자열의 길이는 변하지 않으므로 처음에 한 번만 얻어내면 됩니다.

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

문제

문제

출처

ICPC

9935번 시간초과ㅠㅠㅠㅠ

rindo98 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말