글 읽기 - 시간초과 도와주십쇼

octo756 7년 전 0

재귀함수 때문에 시간초과 발생하는 것 같은데

고수분들 이런경우

어떻게 하시나요??

설마 재귀함수 안쓰는 방법으로 다시 짜시나요??

#include <iostream>
#include <string>
using namespace std;
string srr;
int minSize = 1;
void bombing(string bomb){

	for (int i = 0; i < srr.size() - bomb.size(); i++){
		int check = 1;
		for (int j = i; j < i + bomb.size(); j++){
			if (srr[j] != bomb[j - i]){ check *= 0; }
		}
		if (check != 0){
			for (int k = i; k < srr.size() - bomb.size(); k++){
				srr[k] = srr[k + bomb.size()];
			}
			for (int k = srr.size() - bomb.size(); k < srr.size(); k++){
				minSize++;
			}
			bombing(bomb);
		}
	}
}
int main(){
	string answer, bomb;
	cin >> srr >> bomb;
	answer = srr;

	bombing(bomb);

	if (srr == answer)
		cout << "FRULA";
	else
		for (int i = 0; i <= srr.size() - minSize; i++){
			cout << srr[i];
		}
}

yukariko 7년 전 0

저는 재귀함수로 해결했습니다.

코드의 시간복잡도가 대략 O(N^2) 인것같은데

N이 10만이기때문에 재귀를 쓰지않아도 시간초과가 날것 같습니다.

이 문제는 O(N)으로 해결이 가능합니다.

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

문제

문제

출처

ICPC

시간초과 도와주십쇼

octo756 7년 전 0

yukariko 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말